📑 Table of Contents▼

ゲーデル賞 (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（英語版）, シャフィ・ゴールドワッサー（2回目）, 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 ノガ・アロン , ヨシ・マティアス, 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 ダニエル・スピールマン（2回目）, 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]
2023 Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf
2024 Ryan Williams
2025 Eshan Chattopadhyay, David Zuckerman
2026 Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart

受賞論文

編集
  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, MR 1888797, https://www.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. MR 2001745. 
  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. MR 2090557. 
  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 0004-5411. 
  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”. (2012年5月16日). オリジナルの2013年7月18日時点におけるアーカイブ。. https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012 2012年5月16日閲覧。 
  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. 2017年3月29日閲覧。
  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日閲覧。