計算理論シンポジウム

ACM計算理論シンポジウム( STOC ) は、理論計算機科学の分野における学術会議です。STOC は 1969 年以来毎年開催されており、通常は 5 月か 6 月に開催されます。この会議は、計算機協会の特別利益団体SIGACTが主催しています。1970 年から 2012 年までの STOC の平均採択率は 31% で、2012 年は 29% でした。^[1]

Fich (1996) が書いているように、STOC とその年次IEEE対応会議である FOCS (コンピュータサイエンスの基礎に関するシンポジウム) は、理論計算機科学における 2 大会議であると考えられています。 ^[2]広い意味では、これらは「計算理論全体にわたる最高の研究のためのフォーラムであり、計算理論研究者の幅を広げ、コミュニティの一体化を促進する」ものです。Johnson (1984) は、STOC と FOCS への定期的な出席を、理論計算機科学者のいくつかの特徴の 1 つに挙げています。

理論計算機科学における優れた論文に贈られるゲーデル賞は、STOC と国際オートマトン・言語・プログラミング会議 (ICALP) で交互に授与されます。計算機科学の基礎に対する優れた貢献に贈られるクヌース賞は、STOC とFOCSで交互に授与されます。

2003年以来、STOCは会議で最も質の高い論文を表彰するために、1つ以上のベストペーパー賞^{[3]を授与してきました。さらに、STOCで学生のみが執筆した最優秀論文の著者には、ダニー・ルーウィン・ベスト学生論文賞が授与されます。 [4]この賞は、インターネット企業}アカマイ・テクノロジーズの共同設立者であり、9月11日の攻撃の最初の犠牲者の一人であるアメリカ系イスラエル人の数学者および起業家であるダニエル・M・ルーウィンに敬意を表して名付けられました。^[5]

STOCは1969年5月5日から7日に米国カリフォルニア州マリナデルレイで初めて開催されました。会議議長はパトリック・C・フィッシャーで、プログラム委員会はマイケル・A・ハリソン、ロバート・W・フロイド、ジュリス・ハートマニス、リチャード・M・カープ、アルバート・R・マイヤー、ジェフリー・D・ウルマンで構成されていました。^[6]

STOC の初期の重要な論文には、 NP 完全性の概念を導入した Cook (1971) が含まれます( Cook–Levin の定理も参照)。

STOC は、1992 年、1994 年、2002 年、2008 年、2017 年にカナダで開催され、2001 年にはギリシャで、2020 年と 2021 年には仮想/オンライン会議として、2022 年にはイタリアで開催されました。1969 年から 2023 年までのその他の会議はすべて米国で開催されています。STOC は、1993 年、1996 年、1999 年、2003 年、2007 年、2011 年、2015 年、2019 年、2023 年に Federated Computing Research Conference (FCRC)の一部でした。

2004

Éva Tardos (2004)、「ネットワーク ゲーム」、第 36 回 ACM コンピューティング理論シンポジウム議事録 - STOC '04、pp.  341– 342、doi :10.1145/1007352.1007356、ISBN 978-1581138528、S2CID  18249534

Avi Wigderson (2004)、「幅広さによる深さ、あるいはなぜ他の分野の講演に出席すべきか?」、第 36 回 ACM コンピューティング理論シンポジウム議事録 - STOC '04、p. 579、doi :10.1145/1007352.1007359、ISBN 978-1581138528、S2CID  27563516

2005

ランス・フォートナウ(2005)、「NPを超えて: ラリー・ストックマイヤーの業績と遺産」、第37回ACMコンピューティング理論シンポジウム議事録 - STOC '05、p. 120、doi :10.1145/1060590.1060609、ISBN 978-1581139600、S2CID  16558679

2006

Prabhakar Raghavan (2006)、「ウェブ検索の変化: アルゴリズム、オークション、広告」、第 38 回 ACM コンピューティング理論シンポジウム議事録 - STOC '06、p. 129、doi :10.1145/1132516.1132535、ISBN 978-1595931344、S2CID  19222958

ラッセル・インパグリアッツォ(2006)、「すべてのランダム化アルゴリズムはデランダム化できるか?」、第 38 回 ACM コンピューティング理論シンポジウム議事録 - STOC '06、pp.  373– 374、doi :10.1145/1132516.1132571、ISBN 978-1595931344、S2CID  22433370

2007

ナンシー・リンチ(2007)、「分散コンピューティング理論: アルゴリズム、不可能性の結果、モデル、および証明」、第 39 回 ACM コンピューティング理論シンポジウム議事録 - STOC '07、p. 247、doi :10.1145/1250790.1250826、ISBN 9781595936318、S2CID  22140755

2008

ジェニファー・レックスフォード(2008)、「インターネットルーティングの再考」、第40回ACMコンピューティング理論シンポジウム議事録 - STOC 08、pp.  55– 56、doi :10.1145/1374376.1374386、ISBN 9781605580470、S2CID  10958242

David Haussler (2008)、「人間が人間になった経緯の計算」、第40回ACM計算理論シンポジウム議事録 - STOC 08、pp.  639– 640、doi :10.1145/1374376.1374468、ISBN 9781605580470、S2CID  30452365

ライアン・オドネル(2008)、「ブール関数の解析に関するいくつかのトピック」、第 40 回 ACM コンピューティング理論シンポジウム議事録 - STOC 08、pp.  569– 578、doi :10.1145/1374376.1374458、ISBN 9781605580470、S2CID  1241681

2009

Shafi Goldwasser (2009)、「Athena 講演: プログラムへのアクセス制御?」、第 41 回 ACM シンポジウムの議事録、コンピューティング理論に関するシンポジウム - STOC '09、pp.  167– 168、doi : 10.1145/1536414.1536416、ISBN 9781605585062

2010

David S. Johnson (2010)、「近似アルゴリズムの理論と実践」(クヌース賞講演)

2011

レスリー・G・ヴァリアント（2011）「自然の機械的説明の範囲と限界」（2010 ACM チューリング賞講演）

ラヴィ・カンナン(2011)、「アルゴリズム: 最近の注目点と課題」(2011 年クヌース賞講演)

David A. Ferruci (2011)、「IBM の Watson/DeepQA」(FCRC 全体会議講演)

Luiz Andre Barroso (2011)、「ウェアハウス規模のコンピューティング: 10 代への突入」(FCRC 全体会議講演)

2013

ゲイリー・ミラー（2013）、クヌース賞講演

Prabhakar Raghavan (2013)、全体講演

2014

Thomas Rothvoss (2014)、「マッチング多面体は指数関数的な拡張複雑性を持つ」

シャフィ・ゴールドワッサー(2014)、「暗号レンズ」(チューリング賞講演)ビデオ

シルヴィオ・ミカリ(2014)、「シルヴィオによる証明」(チューリング賞講演)ビデオ

2015

マイケル・ストーンブレーカー（2015）、チューリング賞講演ビデオ

アンドリュー・ヤオ（2015）、FCRC基調講演

ラスロー・ババイ(2015)、クヌース賞講演会

オリヴィエ・テマン (2015)、FCRC 基調講演

2016

Santosh Vempala (2016)、「高次元におけるサンプリングと最適化の相互作用」(招待講演)

Timothy Chan (2016)、「低次元から高次元までの計算幾何学」(招待講演)

2017

Avi Wigderson (2017)、「ToC の性質と将来について」(基調講演)

Orna Kupferman (2017)、「形式検証手法の観点から見た古典的なグラフ理論の問題の検討」(基調講演)

オデッド・ゴールドライヒ（2017）、クヌース賞講演

• 理論計算機科学に関する会議。
• コンピュータ サイエンス カンファレンスのリストには、コンピュータ サイエンスの他の学術カンファレンスが含まれています。
• コンピュータサイエンスの賞一覧

• クック、スティーブン(1971)、「定理証明手順の複雑さ」(PDF)、Proc. STOC 1971、pp.  151– 158、doi : 10.1145/800157.805047、S2CID  7573663。
• Fich, Faith (1996)、「コンピューティング研究の理論に関連するインフラストラクチャの問題」、ACM Computing Surveys、28 (4es): 217–es、doi :10.1145/242224.242502、S2CID  195706843。
• ジョンソン、DS (1984)、「理論計算機科学の系譜：予備報告」、ACM SIGACT News、16 (2): 36– 49、doi :10.1145/1008959.1008960、S2CID  26789249。

• 公式サイト
• DBLPの STOC 議事録情報。
• ACM デジタル ライブラリの STOC プロシーディング。
• FOCS/STOC/SODA の引用統計、Piotr IndykおよびSuresh Venkatasubramanian、2007 年 7 月。