Gödel Prize

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.^[1]

The Gödel Prize has been awarded since 1993. The prize is awarded alternately at ICALP (even years) and STOC (odd years). STOC is the ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science, whereas ICALP is the International Colloquium on Automata, Languages and Programming, one of the main European conferences in the field. To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years. The prize includes a reward of US$5000.^[2]

The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT.

In contrast with the Gödel Prize, which recognizes outstanding papers, the Knuth Prize is awarded to individuals for their overall impact in the field.

Recipients

受賞論文

↑ Babai, László; Moran, Shlomo (1988)、「アーサー・マーリンゲーム：ランダム化証明システムと複雑性クラスの階層」（PDF）、Journal of Computer and System Sciences、36（2）：254–276、doi：10.1016/0022-0000(88)90028-1、ISSN 0022-0000
↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "対話型証明システムの知識複雑性" (PDF) , SIAM Journal on Computing , 18 (1): 186– 208, CiteSeerX 10.1.1.397.4002 , doi : 10.1137/0218012 , ISSN 1095-7111
↑ Håstad, Johan (1989)、「小深度回路のほぼ最適な下限値」(PDF)、Micali, Silvio (編)、ランダム性と計算、Advances in Computing Research、第5巻、JAI Press、6–20ページ、ISBN 978-0-89232-896-32012年2月22日にオリジナル（PDF）からアーカイブされました
↑ Immerman, Neil (1988), "非決定性空間は補元に関して閉じている" (PDF) , SIAM Journal on Computing , 17 (5): 935– 938, CiteSeerX 10.1.1.54.5941 , doi : 10.1137/0217058 , ISSN 1095-7111
↑ Szelepcsényi, R. (1988)、「非決定性オートマトンの強制列挙方法」(PDF)、Acta Informatica、26 (3): 279–284、doi : 10.1007/BF00299636、hdl : 10338.dmlcz/120489、S2CID 10838178
↑ Sinclair, A.; Jerrum, M. (1989), "近似計数、一様生成、および高速混合マルコフ連鎖", Information and Computation , 82 (1): 93–133 , doi : 10.1016/0890-5401(89)90067-9 , ISSN 0890-5401
↑ Jerrum, M.; Sinclair, Alistair (1989)、「Approximating the permanent」、SIAM Journal on Computing、18 (6): 1149–1178、CiteSeerX 10.1.1.431.4190、doi : 10.1137/0218077、ISSN 1095-7111
↑ Halpern, Joseph ; Moses, Yoram (1990), "分散環境における知識と共通知識" (PDF) , Journal of the ACM , 37 (3): 549– 587, arXiv : cs/0006009 , doi : 10.1145/79147.79161 , S2CID 52151232
↑戸田誠之助 (1991) 「PPは多項式時間階層と同じくらい難しい」(PDF)、SIAM Journal on Computing、20 (5): 865–877、CiteSeerX 10.1.1.121.1246、doi : 10.1137/0220053、ISSN 1095-7111 、 2016年3月3日にオリジナル(PDF)からアーカイブ、 2010年6月8日取得
↑ Shor, Peter W. (1997), "量子コンピュータ上での素因数分解と離散対数のための多項式時間アルゴリズム", SIAM Journal on Computing , 26 (5): 1484–1509 , arXiv : quant-ph/9508027 , doi : 10.1137/S0097539795293172 , ISSN 1095-7111 , S2CID 2337707
↑ Vardi, Moshe Y.; Wolper, Pierre (1994), "無限計算に関する推論" (PDF) , Information and Computation , 115 (1): 1– 37, doi : 10.1006/inco.1994.1092 , hdl : 2268/116648 , ISSN 0890-5401 , 2011年8月25日にオリジナル(PDF)からアーカイブ済み
↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996)、「インタラクティブ証明とクリーク近似の難しさ」（PDF）、Journal of the ACM、43（2）：268–292、doi：10.1145/226643.226652、ISSN 0004-5411
↑ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP" (PDF) , Journal of the ACM , 45 (1): 70– 122, doi : 10.1145/273865.273901 , ISSN 0004-5411 , S2CID 751563 , 2011年6月10日にオリジナル(PDF)からアーカイブ済み
↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems" (PDF) , Journal of the ACM , 45 (3): 501– 555, CiteSeerX 10.1.1.145.4652 , doi : 10.1145/278298.278306 , ISSN 0004-5411 , S2CID 8561542 , 2011年6月10日にオリジナル(PDF)からアーカイブ済み
↑ Sénizergues, Géraud (2001), "L(A) = L(B)? 完全な形式システムからの決定可能性の結果", Theor. Comput. Sci. , 251 (1): 1– 166, doi : 10.1016/S0304-3975(00)00285-1 , ISSN 0304-3975
↑ Freund, Y.; Schapire, RE (1997)、「オンライン学習の決定理論的一般化とブースティングへの応用」（PDF）、Journal of Computer and System Sciences、55（1）：119–139、doi：10.1006/jcss.1997.1504、ISSN 1090-2724
↑ Herlihy, Maurice ; Shavit, Nir (1999), "非同期計算可能性のトポロジー構造" (PDF) , Journal of the ACM , 46 (6): 858– 923, CiteSeerX 10.1.1.78.1455 , doi : 10.1145/331524.331529 , S2CID 5797174 ゲーデル賞受賞講演
↑ Saks, Michael ; Zaharoglou, Fotios (2000), "Wait-free k -set agreement is impossible: The topology of public knowledge", SIAM Journal on Computing , 29 (5): 1449– 1483, doi : 10.1137/S0097539796307698
↑ Alon, Noga ; Matias, Yossi; Szegedy, Mario (1999)、「周波数モーメントの近似における空間複雑性」（PDF）、Journal of Computer and System Sciences、58（1）：137–147、doi：10.1006/jcss.1997.15451996年の理論計算機科学シンポジウム（STOC）で初めて発表された。
↑ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P", Annals of Mathematics , 160 (2): 781–793 , doi : 10.4007/annals.2004.160.781 , ISSN 0003-486X
↑ Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences , 55 (1): 24–35 , doi : 10.1006/jcss.1997.1494 , ISSN 0022-0000 , ECCC TR94-010
↑ Spielman, Daniel A.; Teng, Shang-Hua (2004), "アルゴリズムの平滑化解析：なぜシンプレックス法は通常多項式時間を要するのか", J. ACM , 51 (3): 385– 463, arXiv : math/0212413 , doi : 10.1145/990308.990310 , ISSN 0004-5411
↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "エントロピー波、ジグザググラフ積、および新しい定数次数エキスパンダー", Annals of Mathematics , 155 (1): 157– 187, CiteSeerX 10.1.1.236.8669 , doi : 10.2307/3062153 , ISSN 0003-486X , JSTOR 3062153 , MR 1888797 , S2CID 120739405
↑ Reingold, Omer (2008)、「対数空間における無向連結性」、J. ACM、55 (4): 1–24、doi : 10.1145/1391289.1391291、ISSN 0004-5411、S2CID 207168478
↑ Arora, Sanjeev (1998), "ユークリッド巡回セールスマン問題およびその他の幾何学的問題に対する多項式時間近似スキーム", Journal of the ACM , 45 (5): 753– 782, CiteSeerX 10.1.1.23.6765 , doi : 10.1145/290179.290180 , ISSN 0004-5411 , S2CID 3023351
↑ Mitchell, Joseph SB (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing , 28 (4): 1298– 1309, doi : 10.1137/S0097539796309764 , ISSN 1095-7111
↑ Håstad, Johan (2001), "Some optimal inapproximability results" (PDF) , Journal of the ACM , 48 (4): 798– 859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145/502090.502098 , ISSN 0004-5411 , S2CID 5120748
↑クツウピアス、エリアス。パパディミトリウ、クリストス (2009)。「最悪の均衡」。コンピュータサイエンスのレビュー。3 (2): 65–69。土井: 10.1016/j.cosrev.2009.04.003。
↑ Roughgarden, Tim; Tardos, Éva (2002). "利己的なルーティングはどれほど悪いのか？". Journal of the ACM . 49 (2): 236– 259. CiteSeerX 10.1.1.147.1081 . doi : 10.1145/506147.506153 . S2CID 207638789 .
↑ Nisan, Noam; Ronen, Amir (2001). "アルゴリズム的メカニズム設計". Games and Economic Behavior . 35 ( 1–2 ): 166–196 . CiteSeerX 10.1.1.21.1731 . doi : 10.1006/game.1999.0790 .
↑ Boneh, Dan; Franklin, Matthew ( 2003). "Weilペアリングに基づくIDベース暗号化". SIAM Journal on Computing . 32 (3): 586–615 . CiteSeerX 10.1.1.66.1131 . doi : 10.1137/S0097539701398521 . MR 2001745 .
↑ Joux, Antoine (2004). "A one round protocol for tripartite Diffie-Hellman" . Journal of Cryptology . 17 (4): 263– 276. doi : 10.1007/s00145-004-0312-y . MR 2090557 . S2CID 3350730 .
↑ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "ミドルウェアのための最適な集約アルゴリズム". Journal of Computer and System Sciences . 66 (4): 614–656 . arXiv : cs/0204046 . doi : 10.1016/S0022-0000(03)00026-6 .
↑ Spielman, Daniel A.; Teng, Shang -Hua (2011). "Spectral Sparsification of Graphs". SIAM Journal on Computing . 40 (4): 981–1025 . arXiv : 0808.4134 . doi : 10.1137/08074489X . ISSN 0097-5397 . S2CID 9646279 .
↑ Spielman, Daniel A.; Teng, Shang-Hua (2013). "大規模グラフのための局所クラスタリングアルゴリズムとそのほぼ線形時間グラフ分割への応用". SIAM Journal on Computing . 42 (1): 1–26 . arXiv : 0809.3232 . doi : 10.1137/080744888 . ISSN 0097-5397 . S2CID 9151077 .
↑ Spielman, Daniel A.; Teng, Shang-Hua (2014). "対称で対角優位な線形システムの事前処理と解法のためのほぼ線形時間アルゴリズム". SIAM Journal on Matrix Analysis and Applications . 35 (3): 835– 885. arXiv : cs/0607105 . doi : 10.1137/090771430 . ISSN 0895-4798 . S2CID 1750944 .
↑ Brookes, Stephen (2007). "並行分離論理のセマンティクス" (PDF) . Theoretical Computer Science . 375 ( 1– 3): 227– 270. doi : 10.1016/j.tcs.2006.12.034 .
↑ O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF) . Theoretical Computer Science . 375 ( 1– 3): 271– 307. doi : 10.1016/j.tcs.2006.12.035 .
↑ Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (編). Calibrating Noise to Sensitivity in Private Data Analysis . Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284 . doi : 10.1007/11681878_14 . ISBN 978-3-540-32731-8。
↑ Regev, Oded (2009). "格子、エラー学習、ランダム線形コード、および暗号について". Journal of the ACM . 56 (6): 1– 40. CiteSeerX 10.1.1.215.3543 . doi : 10.1145/1568318.1568324 . S2CID 207156623 .
↑ディヌール、イリット (2007)。「ギャップ増幅による PCP 定理」。ACM のジャーナル。54 (3): 12-es。土井: 10.1145/1236457.1236459。S2CID 53244523。
↑ 「一般ロヴァーシュ局所補題の構成的証明」。ACMジャーナル。57 （ 2）。2010年。doi ： 10.1145 /1667053。ISSN 0004-5411。
↑ Bulatov, Andrei A. (2013). "カウント制約充足問題の複雑性". Journal of the ACM . 60 (5). Association for Computing Machinery: 1– 41. doi : 10.1145/2528400 . ISSN 0004-5411 . S2CID 8964233 .
↑ Dyer, Martin; Richerby, David (2013). "An Effective Dichotomy for the Counting Constraint Satisfaction Problem". SIAM Journal on Computing . 42 (3). Society for Industrial & Applied Mathematics (SIAM): 1245–1274 . arXiv : 1003.3879 . doi : 10.1137/100811258 . ISSN 0097-5397 . S2CID 1247279 .
↑ Cai, Jin-Yi; Chen, Xi (2017-06-22). "Complexity of Counting CSP with Complex Weights". Journal of the ACM . 64 (3). Association for Computing Machinery: 1– 39. arXiv : 1111.2384 . doi : 10.1145/2822891 . ISSN 0004-5411 . S2CID 1053684 .
↑ブレーキルスキー、ズヴィカ。ヴァイクンタナタン、ヴィノード（2014 年 1 月）。「(標準) $\mathsf{LWE}$ による効率的な完全準同型暗号化」。SIAM ジャーナルオンコンピューティング。43 (2): 831–871 .土井: 10.1137/120868669。hdl : 1721.1/115488。ISSN 0097-5397。S2CID 8831240。
↑ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "(Leveled) fully homomorphic encryption without bootstrapping" . Proceedings of the 3rd Innovations in Theoretical Computer Science Conference . New York, New York, USA: ACM Press. pp. 309–325 . doi : 10.1145/2090236.2090262 . ISBN 9781450311151. S2CID 2602543 .
↑フィオリーニ、サミュエル。マサール、セルジュ。ポクッタ、セバスチャン。ティワリー、ハンス・ラージ。デ・ウルフ、ロナルド（2015）。「組み合わせ最適化におけるポリトープの指数関数的下限」。ACM のジャーナル。62 (2): 17:1–17:23。arXiv : 1111.0837。土井：10.1145/2716307。S2CID 7372000。
↑ Rothvoss, Thomas (2017). "マッチング多面体は指数関数的な拡張複雑性を持つ" . Journal of the ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi : 10.1145/3127497 . S2CID 47045361 .
↑ウィリアムズ、ライアン（2011年6月）「非均一ACC回路の下限」 2011 IEEE第26回計算複雑性年次会議IEEE pp. 115–125 . doi : 10.1109/ccc.2011.36 . ISBN 978-1-4577-0179-5。
↑ Chattopadhyay, Eshan; Zuckerman, David (2016年6月) 「明示的な2ソース抽出器と耐障害性関数」 .第48回ACM理論計算機科学シンポジウム論文集. ACM. pp. 670–683 . doi : 10.1145/2897518.2897528 . ISBN 978-1-4503-4132-5。
↑ Diakonikolas, Ilias; Kamath, Gautam; Kane, Daniel; Li, Jerry; Moitra, Ankur; Stewart, Alistair (2019). "計算上の困難さを伴わない高次元におけるロバストな推定器". SIAM Journal on Computing . 48 (2): 742–864 . arXiv : 1604.06443 . doi : 10.1137/17M1126680 .

注記

↑ 「ゲーデルの手紙」。2009年2月12日。
1 2 「2017年ゲーデル賞」。欧州理論計算機科学協会。EATCS 。 2017年3月29日取得。
↑ 「アルゴリズムゲーム理論の成長の基礎を築いた3つの論文」。2012年5月16日。 2013年7月18日にオリジナルからアーカイブ。2012年5月16日に取得。
↑ ACMグループが暗号技術の進歩に対してゲーデル賞を授与：セキュリティを向上させる革新で3人のコンピュータ科学者が表彰される2013年6月1日にWayback Machineにアーカイブ済み、 Association for Computing Machinery、2013年5月29日。
↑受賞者は、複数のソースからのデータ集約において画期的な成果を達成しました、 Association for Computing Machinery、2014年4月30日。
↑ 2015年ゲーデル賞発表、Association for Computing MachineryによりWayback Machineに2017年12月9日にアーカイブされました。
↑ 「2018年ゲーデル賞受賞理由」
↑ 「2019年ゲーデル賞受賞理由」
↑ 「2020年ゲーデル賞受賞理由」
↑ 「2021年ゲーデル賞受賞理由」
↑ 「2022年ゲーデル賞受賞理由」。EATCS 。
↑ 「2023年ゲーデル賞受賞理由」。EATCS 。
↑ 「2024年ゲーデル賞受賞理由」。EATCS 。
↑ 「2025年ゲーデル賞受賞理由」
↑ 「2026年ゲーデル賞」

参考文献

当選者リストが掲載されている賞品ウェブサイト

[3] Babai, László; Moran, Shlomo (1988)、「アーサー・マーリンゲーム：ランダム化証明システムと複雑性クラスの階層」（PDF）、Journal of Computer and System Sciences、36（2）：254–276、doi：10.1016/0022-0000(88)90028-1、ISSN 0022-0000

[4] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "対話型証明システムの知識複雑性" (PDF) , SIAM Journal on Computing , 18 (1): 186– 208, CiteSeerX 10.1.1.397.4002 , doi : 10.1137/0218012 , ISSN 1095-7111

[5] Håstad, Johan (1989)、「小深度回路のほぼ最適な下限値」(PDF)、Micali, Silvio (編)、ランダム性と計算、Advances in Computing Research、第5巻、JAI Press、6–20ページ、ISBN 978-0-89232-896-32012年2月22日にオリジナル（PDF）からアーカイブされました

[6] Immerman, Neil (1988), "非決定性空間は補元に関して閉じている" (PDF) , SIAM Journal on Computing , 17 (5): 935– 938, CiteSeerX 10.1.1.54.5941 , doi : 10.1137/0217058 , ISSN 1095-7111

[7] Szelepcsényi, R. (1988)、「非決定性オートマトンの強制列挙方法」(PDF)、Acta Informatica、26 (3): 279–284、doi : 10.1007/BF00299636、hdl : 10338.dmlcz/120489、S2CID 10838178

[8] Sinclair, A.; Jerrum, M. (1989), "近似計数、一様生成、および高速混合マルコフ連鎖", Information and Computation , 82 (1): 93–133 , doi : 10.1016/0890-5401(89)90067-9 , ISSN 0890-5401

[9] Jerrum, M.; Sinclair, Alistair (1989)、「Approximating the permanent」、SIAM Journal on Computing、18 (6): 1149–1178、CiteSeerX 10.1.1.431.4190、doi : 10.1137/0218077、ISSN 1095-7111

[10] Halpern, Joseph ; Moses, Yoram (1990), "分散環境における知識と共通知識" (PDF) , Journal of the ACM , 37 (3): 549– 587, arXiv : cs/0006009 , doi : 10.1145/79147.79161 , S2CID 52151232

[11] 戸田誠之助 (1991) 「PPは多項式時間階層と同じくらい難しい」(PDF)、SIAM Journal on Computing、20 (5): 865–877、CiteSeerX 10.1.1.121.1246、doi : 10.1137/0220053、ISSN 1095-7111 、 2016年3月3日にオリジナル(PDF)からアーカイブ、 2010年6月8日取得

[12] Shor, Peter W. (1997), "量子コンピュータ上での素因数分解と離散対数のための多項式時間アルゴリズム", SIAM Journal on Computing , 26 (5): 1484–1509 , arXiv : quant-ph/9508027 , doi : 10.1137/S0097539795293172 , ISSN 1095-7111 , S2CID 2337707

[13] Vardi, Moshe Y.; Wolper, Pierre (1994), "無限計算に関する推論" (PDF) , Information and Computation , 115 (1): 1– 37, doi : 10.1006/inco.1994.1092 , hdl : 2268/116648 , ISSN 0890-5401 , 2011年8月25日にオリジナル(PDF)からアーカイブ済み

[14] Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996)、「インタラクティブ証明とクリーク近似の難しさ」（PDF）、Journal of the ACM、43（2）：268–292、doi：10.1145/226643.226652、ISSN 0004-5411

[15] Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP" (PDF) , Journal of the ACM , 45 (1): 70– 122, doi : 10.1145/273865.273901 , ISSN 0004-5411 , S2CID 751563 , 2011年6月10日にオリジナル(PDF)からアーカイブ済み

[16] Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems" (PDF) , Journal of the ACM , 45 (3): 501– 555, CiteSeerX 10.1.1.145.4652 , doi : 10.1145/278298.278306 , ISSN 0004-5411 , S2CID 8561542 , 2011年6月10日にオリジナル(PDF)からアーカイブ済み

[17] Sénizergues, Géraud (2001), "L(A) = L(B)? 完全な形式システムからの決定可能性の結果", Theor. Comput. Sci. , 251 (1): 1– 166, doi : 10.1016/S0304-3975(00)00285-1 , ISSN 0304-3975

[18] Freund, Y.; Schapire, RE (1997)、「オンライン学習の決定理論的一般化とブースティングへの応用」（PDF）、Journal of Computer and System Sciences、55（1）：119–139、doi：10.1006/jcss.1997.1504、ISSN 1090-2724

[19] Herlihy, Maurice ; Shavit, Nir (1999), "非同期計算可能性のトポロジー構造" (PDF) , Journal of the ACM , 46 (6): 858– 923, CiteSeerX 10.1.1.78.1455 , doi : 10.1145/331524.331529 , S2CID 5797174 ゲーデル賞受賞講演

[20] Saks, Michael ; Zaharoglou, Fotios (2000), "Wait-free k -set agreement is impossible: The topology of public knowledge", SIAM Journal on Computing , 29 (5): 1449– 1483, doi : 10.1137/S0097539796307698

[21] Alon, Noga ; Matias, Yossi; Szegedy, Mario (1999)、「周波数モーメントの近似における空間複雑性」（PDF）、Journal of Computer and System Sciences、58（1）：137–147、doi：10.1006/jcss.1997.15451996年の理論計算機科学シンポジウム（STOC）で初めて発表された。

[22] Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P", Annals of Mathematics , 160 (2): 781–793 , doi : 10.4007/annals.2004.160.781 , ISSN 0003-486X

[23] Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences , 55 (1): 24–35 , doi : 10.1006/jcss.1997.1494 , ISSN 0022-0000 , ECCC TR94-010

[24] Spielman, Daniel A.; Teng, Shang-Hua (2004), "アルゴリズムの平滑化解析：なぜシンプレックス法は通常多項式時間を要するのか", J. ACM , 51 (3): 385– 463, arXiv : math/0212413 , doi : 10.1145/990308.990310 , ISSN 0004-5411

[25] Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "エントロピー波、ジグザググラフ積、および新しい定数次数エキスパンダー", Annals of Mathematics , 155 (1): 157– 187, CiteSeerX 10.1.1.236.8669 , doi : 10.2307/3062153 , ISSN 0003-486X , JSTOR 3062153 , MR 1888797 , S2CID 120739405

[26] Reingold, Omer (2008)、「対数空間における無向連結性」、J. ACM、55 (4): 1–24、doi : 10.1145/1391289.1391291、ISSN 0004-5411、S2CID 207168478

[27] Arora, Sanjeev (1998), "ユークリッド巡回セールスマン問題およびその他の幾何学的問題に対する多項式時間近似スキーム", Journal of the ACM , 45 (5): 753– 782, CiteSeerX 10.1.1.23.6765 , doi : 10.1145/290179.290180 , ISSN 0004-5411 , S2CID 3023351

[28] Mitchell, Joseph SB (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing , 28 (4): 1298– 1309, doi : 10.1137/S0097539796309764 , ISSN 1095-7111

[29] Håstad, Johan (2001), "Some optimal inapproximability results" (PDF) , Journal of the ACM , 48 (4): 798– 859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145/502090.502098 , ISSN 0004-5411 , S2CID 5120748

[31] クツウピアス、エリアス。パパディミトリウ、クリストス (2009)。「最悪の均衡」。コンピュータサイエンスのレビュー。3 (2): 65–69。土井: 10.1016/j.cosrev.2009.04.003。

[32] Roughgarden, Tim; Tardos, Éva (2002). "利己的なルーティングはどれほど悪いのか？". Journal of the ACM . 49 (2): 236– 259. CiteSeerX 10.1.1.147.1081 . doi : 10.1145/506147.506153 . S2CID 207638789 .

[33] Nisan, Noam; Ronen, Amir (2001). "アルゴリズム的メカニズム設計". Games and Economic Behavior . 35 ( 1–2 ): 166–196 . CiteSeerX 10.1.1.21.1731 . doi : 10.1006/game.1999.0790 .

[35] Boneh, Dan; Franklin, Matthew ( 2003). "Weilペアリングに基づくIDベース暗号化". SIAM Journal on Computing . 32 (3): 586–615 . CiteSeerX 10.1.1.66.1131 . doi : 10.1137/S0097539701398521 . MR 2001745 .

[36] Joux, Antoine (2004). "A one round protocol for tripartite Diffie-Hellman" . Journal of Cryptology . 17 (4): 263– 276. doi : 10.1007/s00145-004-0312-y . MR 2090557 . S2CID 3350730 .

[38] Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "ミドルウェアのための最適な集約アルゴリズム". Journal of Computer and System Sciences . 66 (4): 614–656 . arXiv : cs/0204046 . doi : 10.1016/S0022-0000(03)00026-6 .

[SpielmanTeng2011-40] Spielman, Daniel A.; Teng, Shang -Hua (2011). "Spectral Sparsification of Graphs". SIAM Journal on Computing . 40 (4): 981–1025 . arXiv : 0808.4134 . doi : 10.1137/08074489X . ISSN 0097-5397 . S2CID 9646279 .

[SpielmanTeng2013-41] Spielman, Daniel A.; Teng, Shang-Hua (2013). "大規模グラフのための局所クラスタリングアルゴリズムとそのほぼ線形時間グラフ分割への応用". SIAM Journal on Computing . 42 (1): 1–26 . arXiv : 0809.3232 . doi : 10.1137/080744888 . ISSN 0097-5397 . S2CID 9151077 .

[SpielmanTeng2014-42] Spielman, Daniel A.; Teng, Shang-Hua (2014). "対称で対角優位な線形システムの事前処理と解法のためのほぼ線形時間アルゴリズム". SIAM Journal on Matrix Analysis and Applications . 35 (3): 835– 885. arXiv : cs/0607105 . doi : 10.1137/090771430 . ISSN 0895-4798 . S2CID 1750944 .

[43] Brookes, Stephen (2007). "並行分離論理のセマンティクス" (PDF) . Theoretical Computer Science . 375 ( 1– 3): 227– 270. doi : 10.1016/j.tcs.2006.12.034 .

[44] O'Hearn, Peter (2007). "Resources, Concurrency and Local Reasoning" (PDF) . Theoretical Computer Science . 375 ( 1– 3): 271– 307. doi : 10.1016/j.tcs.2006.12.035 .

[45] Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (編). Calibrating Noise to Sensitivity in Private Data Analysis . Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284 . doi : 10.1007/11681878_14 . ISBN 978-3-540-32731-8。

[Regev2009-47] Regev, Oded (2009). "格子、エラー学習、ランダム線形コード、および暗号について". Journal of the ACM . 56 (6): 1– 40. CiteSeerX 10.1.1.215.3543 . doi : 10.1145/1568318.1568324 . S2CID 207156623 .

[Dinur2007-49] ディヌール、イリット (2007)。「ギャップ増幅による PCP 定理」。ACM のジャーナル。54 (3): 12-es。土井: 10.1145/1236457.1236459。S2CID 53244523。

[MoserTardos2010-51] 「一般ロヴァーシュ局所補題の構成的証明」。ACMジャーナル。57 （ 2）。2010年。doi ： 10.1145 /1667053。ISSN 0004-5411。

[Bulatov_2013_pp._1–41-53] Bulatov, Andrei A. (2013). "カウント制約充足問題の複雑性". Journal of the ACM . 60 (5). Association for Computing Machinery: 1– 41. doi : 10.1145/2528400 . ISSN 0004-5411 . S2CID 8964233 .

[Dyer_Richerby_2013_pp._1245–1274-54] Dyer, Martin; Richerby, David (2013). "An Effective Dichotomy for the Counting Constraint Satisfaction Problem". SIAM Journal on Computing . 42 (3). Society for Industrial & Applied Mathematics (SIAM): 1245–1274 . arXiv : 1003.3879 . doi : 10.1137/100811258 . ISSN 0097-5397 . S2CID 1247279 .

[Cai_Chen_pp._1–39-55] Cai, Jin-Yi; Chen, Xi (2017-06-22). "Complexity of Counting CSP with Complex Weights". Journal of the ACM . 64 (3). Association for Computing Machinery: 1– 39. arXiv : 1111.2384 . doi : 10.1145/2822891 . ISSN 0004-5411 . S2CID 1053684 .

[BV11-57] ブレーキルスキー、ズヴィカ。ヴァイクンタナタン、ヴィノード（2014 年 1 月）。「(標準) $\mathsf{LWE}$ による効率的な完全準同型暗号化」。SIAM ジャーナルオンコンピューティング。43 (2): 831–871 .土井: 10.1137/120868669。hdl : 1721.1/115488。ISSN 0097-5397。S2CID 8831240。

[BGV12-58] Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "(Leveled) fully homomorphic encryption without bootstrapping" . Proceedings of the 3rd Innovations in Theoretical Computer Science Conference . New York, New York, USA: ACM Press. pp. 309–325 . doi : 10.1145/2090236.2090262 . ISBN 9781450311151. S2CID 2602543 .

[FMPTW15-60] フィオリーニ、サミュエル。マサール、セルジュ。ポクッタ、セバスチャン。ティワリー、ハンス・ラージ。デ・ウルフ、ロナルド（2015）。「組み合わせ最適化におけるポリトープの指数関数的下限」。ACM のジャーナル。62 (2): 17:1–17:23。arXiv : 1111.0837。土井：10.1145/2716307。S2CID 7372000。

[Rot17-61] Rothvoss, Thomas (2017). "マッチング多面体は指数関数的な拡張複雑性を持つ" . Journal of the ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi : 10.1145/3127497 . S2CID 47045361 .

[63] ウィリアムズ、ライアン（2011年6月）「非均一ACC回路の下限」 2011 IEEE第26回計算複雑性年次会議IEEE pp. 115–125 . doi : 10.1109/ccc.2011.36 . ISBN 978-1-4577-0179-5。

[65] Chattopadhyay, Eshan; Zuckerman, David (2016年6月) 「明示的な2ソース抽出器と耐障害性関数」 .第48回ACM理論計算機科学シンポジウム論文集. ACM. pp. 670–683 . doi : 10.1145/2897518.2897528 . ISBN 978-1-4503-4132-5。

[67] Diakonikolas, Ilias; Kamath, Gautam; Kane, Daniel; Li, Jerry; Moitra, Ankur; Stewart, Alistair (2019). "計算上の困難さを伴わない高次元におけるロバストな推定器". SIAM Journal on Computing . 48 (2): 742–864 . arXiv : 1604.06443 . doi : 10.1137/17M1126680 .

[1] 「ゲーデルの手紙」。2009年2月12日。

[Godël2017-2] 1 2 「2017年ゲーデル賞」。欧州理論計算機科学協会。EATCS 。 2017年3月29日取得。

[sigact-2012-30] 「アルゴリズムゲーム理論の成長の基礎を築いた3つの論文」。2012年5月16日。 2013年7月18日にオリジナルからアーカイブ。2012年5月16日に取得。

[34] ACMグループが暗号技術の進歩に対してゲーデル賞を授与：セキュリティを向上させる革新で3人のコンピュータ科学者が表彰される2013年6月1日にWayback Machineにアーカイブ済み、 Association for Computing Machinery、2013年5月29日。

[37] 受賞者は、複数のソースからのデータ集約において画期的な成果を達成しました、 Association for Computing Machinery、2014年4月30日。

[39] 2015年ゲーデル賞発表、Association for Computing MachineryによりWayback Machineに2017年12月9日にアーカイブされました。

[Godël2018-46] 「2018年ゲーデル賞受賞理由」

[Godël2019-48] 「2019年ゲーデル賞受賞理由」

[Godël2020-50] 「2020年ゲーデル賞受賞理由」

[Godël2021-52] 「2021年ゲーデル賞受賞理由」

[56] 「2022年ゲーデル賞受賞理由」。EATCS 。

[59] 「2023年ゲーデル賞受賞理由」。EATCS 。

[62] 「2024年ゲーデル賞受賞理由」。EATCS 。

[64] 「2025年ゲーデル賞受賞理由」

[66] 「2026年ゲーデル賞」

[1]

[2]

Gödel Prize

Recipients

受賞論文

関連項目

注記

参考文献

関連するトピック

theoretical computer science

European Association for Theoretical Computer Science

Association for Computing Machinery

ACM SIGACT