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

STOC2006輪講

STOC 2006 Seminar

STOC 2006 で発表された論文を主に対象としたセミナーです。

趣旨

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

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

形式

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

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

注意事項

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

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

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

発表リスト

現在予定されている発表の一覧です。発表を行いたい、という人は各自以下にエントリを追加していってください。

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 参照の局所性を考慮したページング