ゲーデル賞

ゲーデル賞 (Gödel Prize) は、理論計算機科学分野で優れた功績を残した人に、ACM（国際計算機学会）のアルゴリズムと計算量理論に関する部会とEATCS（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞金5,000ドルが贈られる。論理学者クルト・ゲーデルに由来する。計算機科学分野ではチューリング賞と並んで権威を持つ賞である。

受賞者一覧

Year	受賞者	授賞理由	論文発表年
1993	László Babai（英語版）, シャフィ・ゴールドワッサー, シルビオ・ミカリ, Shlomo Moran（英語版）, Charles Rackoff（英語版）	対話型証明システムの発明	1988,[論文 1] 1989[論文 2]
1994	Johan Håstad（英語版）	パリティ関数の定数深さの回路は、サイズの下界が指数関数となること	1989[論文 3]
1995	Neil Immerman（英語版）, Róbert Szelepcsényi（英語版）	Immerman–Szelepcsényiの定理（英語版）	1988,[論文 4] 1988[論文 5]
1996	Mark Jerrum（英語版）, Alistair Sinclair（英語版）	マルコフ連鎖と行列のパーマネントの近似に対する業績	1989,[論文 6] 1989[論文 7]
1997	Joseph Halpern（英語版）, Yoram Moses（英語版）	分散環境における「知識」の形式概念の定義	1990[論文 8]
1998	戸田誠之助	戸田の定理	1991[論文 9]
1999	ピーター・ショア	ショアのアルゴリズム	1997[論文 10]
2000	Moshe Y. Vardi（英語版）, Pierre Wolper（英語版）	有限オートマトンによる時相論理への業績	1994[論文 11]
2001	Sanjeev Arora（英語版）, Uriel Feige（英語版）, シャフィ・ゴールドワッサー, Carsten Lund（英語版）, ラースロー・ロヴァース, Rajeev Motwani（英語版）, Shmuel Safra（英語版）, Madhu Sudan（英語版）, Mario Szegedy（英語版）	PCP定理（英語版）と近似の困難さへの応用	1996,[論文 12] 1998,[論文 13] 1998[論文 14]
2002	Géraud Sénizergues（英語版）	決定性プッシュダウン・オートマトン（英語版）の等価性が決定可能であることの証明	2001[論文 15]
2003	Yoav Freund（英語版）, Robert Schapire（英語版）	AdaBoost	1997[論文 16]
2004	Maurice Herlihy（英語版）, Michael Saks（英語版）, Nir Shavit（英語版）, Fotios Zaharoglou（英語版）	トポロジーの分散コンピューティングへの応用	1999,[論文 17] 2000[論文 18]
2005	Noga Alon（英語版）, ヨシ・マティアス, Mario Szegedy（英語版）	ストリーミングアルゴリズム（英語版）に対する基本的な貢献	1999[論文 19]
2006	マニンドラ・アグラワル, ニラジュ・カヤル, Nitin Saxena（英語版）	AKS素数判定法	2004[論文 20]
2007	Alexander Razboroven（英語版）, Steven Rudich（英語版）	自然な証明	1997[論文 21]
2008	ダニエル・スピールマン, Shanghua Teng（英語版）	アルゴリズムの平滑化解析（英語版）	2004[論文 22]
2009	Omer Reingold（英語版）, Salil Vadhan（英語版）, アヴィ・ヴィグダーソン	グラフ理論におけるジグザグ積（英語版）およびUSTCONが対数領域で解けること	2002,[論文 23] 2008[論文 24]
2010	Sanjeev Arora（英語版）, Joseph S. B. Mitchell（英語版）	ユークリッド距離に基づく巡回セールスマン問題に対する多項式時間近似スキームの発見	1998,[論文 25] 1999[論文 26]
2011	Johan Håstad（英語版）	さまざまな組み合わせ問題に対する近似不可能性の証明	2001[論文 27]
2012	Elias Koutsoupias（英語版）, クリストス・パパディミトリウ, Noam Nisan（英語版）, Amir Ronen（ドイツ語版）, Tim Roughgarden（英語版）, Éva Tardos（英語版）	アルゴリズム的ゲーム理論（英語版）の基礎を築く[1]	2009,[論文 28] 2002,[論文 29] 2001[論文 30]
2013	Dan Boneh（英語版）, Matthew K. Franklin（英語版）, Antoine Joux（英語版）	マルチパーティディフィー・ヘルマン鍵共有およびBoneh–Franklin scheme（英語版）[2]	2003,[論文 31] 2004[論文 32]
2014	ロナルド・フェイギン, Amnon Lotem（フランス語版）, Moni Naor（英語版）	ミドルウェアのための最適な集約アルゴリズム[3]	2003,[論文 33]
2015	ダニエル・スピールマン, Shanghua Teng（英語版）	ほぼ線形時間のラプラシアンソルバーに関する一連の論文[4]	2011[論文 34], 2013[論文 35], 2014[論文 36]
2016	Stephen Brookes（ドイツ語版）, Peter O'Hearn（英語版）	Concurrent Separation Logic の発明	2007[論文 37], 2007[論文 38]
2017[5]	Cynthia Dwork（英語版）, Frank McSherry（フランス語版）, Kobbi Nissim（英語版）, Adam D. Smith（フランス語版）	differential privacy（英語版）の発明	2006[論文 39]
2018[6]	Oded Regev（英語版）	Learning with errors（英語版）問題の導入	2009[論文 40]
2019[7]	Irit Dinur（英語版）	PCP定理に対する新たな証明	2007[論文 41]
2020[8]	Robin Moser, Gábor Tardos（英語版）	Lovász Local Lemmaに対する構成的な証明	2010[論文 42]
2021[9]	Andrei Bulatov, Jin-Yi Cai（英語版）, Xi Chen（英語版）, Martin Dyer（英語版）, David Richerby	制約充足問題の数え上げの複雑さの分類に関する研究	2013[論文 43] 2013[論文 44] 2017[論文 45]
2022[10]	Zvika Brakerski, Craig Gentry（英語版）, Vinod Vaikuntanathan	効率的な完全準同型暗号の構築による暗号理論への革新的な貢献	2014,[論文 46] 2014[論文 47]

受賞論文

1. Babai, László; Moran, Shlomo (1988), “Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class”, Journal of Computer and System Sciences 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf
2. Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems”, SIAM Journal on Computing 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf
3. Håstad, Johan (1989), “Almost Optimal Lower Bounds for Small Depth Circuits”, in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 978-0-89232-896-3, オリジナルの2012-02-22時点におけるアーカイブ。, http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf
4. Immerman, Neil (1988), “Nondeterministic space is closed under complementation”, SIAM Journal on Computing 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111, http://www.cs.umass.edu/~immerman/pub/space.pdf
5. Szelepcsényi, R. (1988), “The method of forced enumeration for nondeterministic automata”, Acta Informatica 26 (3): 279–284, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489, http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf
6. Sinclair, A.; Jerrum, M. (1989), “Approximate counting, uniform generation and rapidly mixing Markov chains”, Information and Computation 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9, ISSN 0890-5401
7. Jerrum, M.; Sinclair, Alistair (1989), “Approximating the permanent”, SIAM Journal on Computing 18 (6): 1149–1178, doi:10.1137/0218077, ISSN 1095-7111
8. Halpern, Joseph; Moses, Yoram (1990), “Knowledge and common knowledge in a distributed environment”, Journal of the ACM 37 (3): 549–587, arXiv:cs/0006009, doi:10.1145/79147.79161, https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf
9. Toda, Seinosuke (1991), “PP is as hard as the polynomial-time hierarchy”, SIAM Journal on Computing 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111, http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf
10. Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26 (5): 1484–1509, arXiv:quant-ph/9508027, doi:10.1137/S0097539795293172, ISSN 1095-7111
11. Vardi, Moshe Y.; Wolper, Pierre (1994), “Reasoning about infinite computations”, Information and Computation 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, https://doi.org/10.1006/inco.1994.1092
12. Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), “Interactive proofs and the hardness of approximating cliques”, Journal of the ACM 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411, http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf
13. Arora, Sanjeev; Safra, Shmuel (1998), “Probabilistic checking of proofs: a new characterization of NP”, Journal of the ACM 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, https://doi.org/10.1145/273865.273901
14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), “Proof verification and the hardness of approximation problems”, Journal of the ACM 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, https://doi.org/10.1145/278298.278306
15. Sénizergues, Géraud (2001), “L(A) = L(B)? decidability results from complete formal systems”, Theor. Comput. Sci. 251 (1): 1–166, doi:10.1016/S0304-3975(00)00285-1, ISSN 0304-3975
16. Freund, Y.; Schapire, R.E. (1997), “A decision-theoretic generalization of on-line learning and an application to boosting”, Journal of Computer and System Sciences 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724, http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf
17. Herlihy, Maurice; Shavit, Nir (1999), “The topological structure of asynchronous computability”, Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529, http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf. Gödel prize lecture
18. 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
19. Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), “The space complexity of approximating the frequency moments”, Journal of Computer and System Sciences 58 (1): 137–147, doi:10.1006/jcss.1997.1545, http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf. First presented at the Symposium on Theory of Computing (STOC) in 1996.
20. 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, https://doi.org/10.4007/annals.2004.160.781
21. 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
22. Spielman, Daniel A.; Teng, Shang-Hua (2004), “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, J. ACM 51 (3): 385–463, arXiv:math/0212413, doi:10.1145/990308.990310, ISSN 0004-5411
23. Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), “Entropy waves, the zig-zag graph product, and new constant-degree expanders”, Annals of Mathematics 155 (1): 157–187, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR1888797, https://jstor.org/stable/3062153
24. Reingold, Omer (2008), “Undirected connectivity in log-space”, J. ACM 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411
25. Arora, Sanjeev (1998), “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, Journal of the ACM 45 (5): 753–782, doi:10.1145/290179.290180, ISSN 0004-5411
26. Mitchell, Joseph S. B. (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
27. Håstad, Johan (2001), “Some optimal inapproximability results”, Journal of the ACM 48 (4): 798–859, doi:10.1145/502090.502098, ISSN 0004-5411, http://www.nada.kth.se/~johanh/optimalinap.pdf
28. Koutsoupias, Elias; Papadimitriou, Christos (2009). “Worst-case equilibria”. Computer Science Review 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
29. Roughgarden, Tim; Tardos, Éva (2002). “How bad is selfish routing?”. Journal of the ACM 49 (2): 236–259. doi:10.1145/506147.506153.
30. Nisan, Noam; Ronen, Amir (2001). “Algorithmic Mechanism Design”. Games and Economic Behavior 35 (1–2): 166–196. doi:10.1006/game.1999.0790.
31. Boneh, Dan; Franklin, Matthew (2003). “Identity-based encryption from the Weil pairing”. SIAM Journal on Computing 32 (3): 586–615. doi:10.1137/S0097539701398521. MR2001745.
32. 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. MR2090557.
33. Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). “Optimal aggregation algorithms for middleware”. Journal of Computer and System Sciences 66 (4): 614–656. arXiv:cs/0204046. doi:10.1016/S0022-0000(03)00026-6.
34. 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.
35. Spielman, Daniel A.; Teng, Shang-Hua (2013). “A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning”. SIAM Journal on Computing 42 (1): 1–26. arXiv:0809.3232. doi:10.1137/080744888. ISSN 0097-5397.
36. Spielman, Daniel A.; Teng, Shang-Hua (2014). “Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems”. SIAM Journal on Matrix Analysis and Applications 35 (3): 835–885. arXiv:cs/0607105. doi:10.1137/090771430. ISSN 0895-4798.
37. Brookes, Stephen (2007). “A Semantics for Concurrent Separation Logic”. Theoretical Computer Science 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034. https://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf.
38. O'Hearn, Peter (2007). “Resources, Concurrency and Local Reasoning”. Theoretical Computer Science 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035. http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf.
39. Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). 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。
40. Regev, Oded (2009). “On lattices, learning with errors, random linear codes, and cryptography”. Journal of the ACM 56 (6): 1–40. doi:10.1145/1568318.1568324.
41. Dinur, Irit (2007). “The PCP theorem by gap amplification”. Journal of the ACM 54 (3): 12–es. doi:10.1145/1236457.1236459. https://dl.acm.org/citation.cfm?id=1236459.
42. “A constructive proof of the general Lovász Local Lemma”. Journal of the ACM 57 (2). (2010). doi:10.1145/1667053. ISSN 00045411.
43. Bulatov, Andrei A. (2013). “The complexity of the counting constraint satisfaction problem”. Journal of the ACM (Association for Computing Machinery (ACM)) 60 (5): 1-41. doi:10.1145/2528400. ISSN 0004-5411.
44. Dyer, Martin; Richerby, David (2013). “An Effective Dichotomy for the Counting Constraint Satisfaction Problem”. SIAM Journal on Computing (Society for Industrial & Applied Mathematics (SIAM)) 42 (3): 1245-1274. arXiv:1003.3879. doi:10.1137/100811258. ISSN 0097-5397.
45. Cai, Jin-Yi; Chen, Xi (2017-06-22). “Complexity of Counting CSP with Complex Weights”. Journal of the ACM (Association for Computing Machinery (ACM)) 64 (3): 1-39. arXiv:1111.2384. doi:10.1145/2822891. ISSN 0004-5411.
46. Brakerski, Zvika; Vaikuntanathan, Vinod (January 2014). “Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$”. SIAM Journal on Computing 43 (2): 831-871. doi:10.1137/120868669. ISSN 0097-5397. https://doi.org/10.1137/120868669.
47. Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). “(Leveled) fully homomorphic encryption without bootstrapping”. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS '12 (New York, New York, USA: ACM Press). doi:10.1145/2090236.2090262. https://doi.org/10.1145/2090236.2090262.

出典

1. “Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory”. (16 May 2012). オリジナルの18 July 2013時点におけるアーカイブ。. https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012 16 May 2012閲覧。
2. ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Archived 2013-06-01 at the Wayback Machine., Association for Computing Machinery, May 29, 2013.
3. Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
4. 2015 Gödel Prize announcement Archived 2017-12-09 at the Wayback Machine. by Association for Computing Machinery.
5. “2017 Gödel Prize”. European Association for Theoretical Computer Science. EATCS. 29 March 2017閲覧。
6. “2018 Gödel Prize citation”. 2020年9月5日閲覧。
7. “2019 Gödel Prize citation”. 2020年9月5日閲覧。
8. “2020 Gödel Prize citation”. 2020年9月5日閲覧。
9. “2021 Gödel Prize citation”. 2022年8月14日閲覧。
10. “2022 Gödel Prize citation”. 2022年8月14日閲覧。