ゲーデル賞 (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 Daniel Spielman英語版, Shanghua Teng英語版 アルゴリズム平滑化解析英語版 2004[論文 22]
2009 Omer Reingold英語版, Salil Vadhan英語版, Avi Wigderson英語版 グラフ理論におけるジグザグ積英語版および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 Daniel Spielman英語版, 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]

受賞論文編集

  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, 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, オリジナルの2011-08-25時点におけるアーカイブ。, https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf 
  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, オリジナルの2011-06-10時点におけるアーカイブ。, https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf 
  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, オリジナルの2011-06-10時点におけるアーカイブ。, https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf 
  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, オリジナルの2011-06-07時点におけるアーカイブ。, https://web.archive.org/web/20110607101302/http://math.berkeley.edu/~coleman/Courses/Fall08/Cryptography/primality_v6.pdf 
  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). “Calibrating Noise to Sensitivity in Private Data Analysis”. Lecture Notes in Computer Science. 3876. Theory of Cryptography (TCC). 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. 

脚注編集