トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

STOC・FOCS輪講

STOC・FOCS 輪講

国際会議 STOC・FOCS で発表された論文を各自紹介する輪講です。

STOC・FOCS は、どちらも理論計算機科学の分野で最もレベルの高い国際会議です。

  • STOC: Symposium on Theory of Computing Conference アルゴリズム、計算量理論全般
  • FOCS: Symposium on Foundations of Computer Science 計算量理論の論文が多い

趣旨

"論文を手分けして読み、発表することで、個々人が論文読みに費やす時間を短縮すること"、および、"様々な分野の最先端の結果に触れること"が目的です。

各人が好きな論文を読み、1,2時間程度で論文の結果、アイデア、テクニックなどについて紹介を行います。

形式

基本的には各人が面白いと思った論文を読み、発表してもらいます。参加表明は以下の発表リストに各自エントリを追加することで行ってください。ドクターの皆さんだけでなく、修士や学部の方々も(発表を聞くだけでもかまわないので)是非参加してください。

発表の前には members にアナウンスが行われ、話に興味のある人がその都度参加するという形式をとります。全員参加を目的としたものではなく、したがってそれに伴うスケジュール調整なども発生しません。

注意事項

論文の中には、ページ数制限などの影響も有り、完全に読みこなすのは現実的に難しいものもあります。このようなものには無理に時間をかけずにまず周りの人に相談をしてみて、解る範囲で発表をしてください。ただし、最低限、問題設定、論文の結果、過去の結果との比較、メインアイデアなどは明らかにしてもらえるとありがたいです。

部屋の確保、発表日時の設定、membersへのアナウンス等は、発表者各自で行ってください。発表日時が決まり次第、このページの内容を更新して、発表がぶつからないようにしてください。

STOC・FOCS 以外の論文を発表していただいてももちろんかまいません。

発表リスト

  • 1: Pseudorandom bits for polynomials via the Gowers norm
  • 2: Mechanism design via different privacy
  • 3: Can you beat treewidth?
  • 4: Toward sharp inapproximability for any 2-CSP (best student paper)
  • 5: Strongly history-independent hashing with applications
  • 6: Any AND-OR formula size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
  • 7: Refuting smoothed 3CNF formulas
  • 8: Discrepancy and the power of bottom fan-in in depth-three circuits
  • 9: A primal-dual randomized algorithm for weighted paging
  • 10: Testing expansion in bounded-degree graphs
  • 11: Buy-at-bulk network design with protection
  • 12: Approximation algorithms using hierarchies of semidefinete programming relaxations
  • 13: Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Shrijver hierarchy

accepted papers: http://www.focs2007.org/accepted.txt

2007年スケジュール

発表者 発表日 タイトル キーワード、概要等
-- 2007/?/?? -- --

過去の発表

FOCS 2006

proceedings: http://www.stanford.edu/%7Esaberi/focsprogram.html

発表者 発表日 時間・場所 タイトル キーワード、概要等
杉原 2007年5月22日 13時会議室 Minimum Bounded Degree Spanning Trees http://www.lab2.kuis.kyoto-u.ac.jp/~sugihara/ppt/070522FOCS2006.ppt
山本 2007年5月17日 15時会議室 Practical Loss-Resilient Codes (STOC '97) 近年,LDPC 符号は,衛星デジタル・テレビ放送の標準規格「DVB-S2」に採用されるなど,誤り訂正能力が非常に高い符号として注目を集めている.この特性は,今から10年ほど前に,Luby らによって理論的に証明された:Binary Erasure Channel (BEC) 上の通信では,LDPC 符号の効率はシャノン限界を達成する.本講演では彼らの復号化アルゴリズムとその理論的な解析を解説する.
山本 2007年4月17日 12時30分会議室 An Elementary Construction of Constant-Degree Expanders (SODA'07) エキスパンダーグラフとは,(roughly speaking)どのような頂点の2分割に対しても,そのカット辺が多いグラフのことである.ランダムグラフは高い確率でエキスパンダーグラフになるが,一般に,このような構造をもった(次数が定数でエキスパンション率が定数の)グラフを構成的に作ることは難しい.これまでに様々な構成方法が提案されてきたが,それらの証明は他の数学の結果を用いたものであった.本論文では,単純な構成方法を示し,初等的な証明により,そのエキスパンション率がある定数以上であることを示す.http://www.lab2.kuis.kyoto-u.ac.jp/~okia/yamamoto/handout.pdf http://www.lab2.kuis.kyoto-u.ac.jp/~okia/yamamoto/slide.pdf
岡本 2007年3月7日 15時会議室 Algebraic Structures and Algorithms for Matching and Matroid Problems (best student paper) http://www.lab2.kuis.kyoto-u.ac.jp/~okia/20070307FOCS2006.ppt
2006年10月11日 Improved Approximation Algorithms for Multidimensional Bin Packing Problems 研究会にて

STOC 2006

accepted papers 一覧: http://www.cs.washington.edu/stoc06/stoc06program.pdf

proceedingshttp://portal.acm.org/toc.cfm?id=1132516&type=proceeding&coll=ACM&dl=GUIDE&CFID=78506611&CFTOKEN=34959643

発表者 発表日 タイトル キーワード、概要等
田坂 2006/6/23 Truthful Randomized Mechanisms for Combinatorial Auctions Combinatorial Auctions Incentive Compatibility 組み合わせオークションの勝者決定問題はNP困難であることが知られています。そこで、この問題を近似アルゴリズムを用いて多項式時間で解くことを考えます。この論文では、多項式時間で解けて、出来るだけ良い近似率を持ち、なおかつ正直な組み合わせオークションのメカニズムを設計することを目的とし、その研究成果が述べられています。
角田 2006/6/30 New Trade-Offs in Cost-Sharing Mechanisms
山本 2006/10/19 On Basing One-Way Functions on NP-Hardness 現代の(計算論的)暗号理論の多くは,(average-case hard な)one-way function の存在を仮定している.古くから,(*)「NP\not\subset BPP ならば(つまり worst-case hardness を仮定すれば),(average-case hard な)one-way function が存在する」であるか?,という疑問がある.この命題を肯定的に証明する一つの(自然な)方法として,ある NP 完全な言語 L から,ある average-case ``easy'' な関数 f への多項式時間 Turing-reduction を示すことである.本論文では,このような還元という手法による証明が,命題 (*) を示すことの不可能性について論じている.
花谷 2006/11/?? The PCP theorem by gap amplification
川原 2007/5/21 On Adequate Performance Measures for Paging 参照の局所性を考慮したページング

FOCS 2005

FOCS2005のページ

STOC 2005

STOC2005のページ

FOCS 2004

開催されたが記録なし