トップ 一覧 検索 ヘルプ 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

proceedings
http://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のページ|http://www.lab2.kuis.kyoto-u.ac.jp/inside/wiki/wiki.cgi?%ce%d8%b9%d6%a1%a7FOCS2005]

!!! STOC 2005

[STOC2005のページ|http://www.lab2.kuis.kyoto-u.ac.jp/inside/wiki/wiki.cgi?%ce%d8%b9%d6%a1%a7STOC2005]

! FOCS 2004
!!! FOCS 2004

開催されたが記録なし