ゲーデル賞

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

受賞者一覧
Year 受賞者 授賞理由 論文発表年
1993László Babai, シャフィ・ゴールドワッサー, シルビオ・ミカリ, Shlomo Moran, Charles Rackoff対話型証明システムの発明1988,[論文 1] 1989[論文 2]
1994Johan Håstadパリティ関数の定数深さの回路は、サイズの下界が指数関数となること1989[論文 3]
1995Neil Immerman, Róbert SzelepcsényiImmerman–Szelepcsényiの定理1988,[論文 4] 1988[論文 5]
1996Mark Jerrum, Alistair Sinclairマルコフ連鎖と行列のパーマネントの近似に対する業績1989,[論文 6] 1989[論文 7]
1997Joseph Halpern, Yoram Moses分散環境における「知識」の形式概念の定義1990[論文 8]
1998戸田誠之助戸田の定理1991[論文 9]
1999ピーター・ショアショアのアルゴリズム1997[論文 10]
2000Moshe Y. Vardi, Pierre Wolper有限オートマトンによる時相論理への業績1994[論文 11]
2001Sanjeev Arora, Uriel Feige, シャフィ・ゴールドワッサー, Carsten Lund, ラースロー・ロヴァース, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario SzegedyPCP定理と近似の困難さへの応用1996,[論文 12] 1998,[論文 13] 1998[論文 14]
2002Géraud Sénizergues決定性プッシュダウン・オートマトンの等価性が決定可能であることの証明2001[論文 15]
2003Yoav Freund, Robert SchapireAdaBoost1997[論文 16]
2004Maurice Herlihy, Michael Saks, Nir Shavit, Fotios Zaharoglouトポロジーの分散コンピューティングへの応用1999,[論文 17] 2000[論文 18]
2005Noga Alon, ヨシ・マティアス, Mario Szegedyストリーミングアルゴリズムに対する基本的な貢献1999[論文 19]
2006マニンドラ・アグラワル, ニラジュ・カヤル, Nitin SaxenaAKS素数判定法2004[論文 20]
2007Alexander Razboroven, Steven Rudich自然な証明1997[論文 21]
2008ダニエル・スピールマン, Shanghua Tengアルゴリズムの平滑化解析2004[論文 22]
2009Omer Reingold, Salil Vadhan, アヴィ・ヴィグダーソングラフ理論におけるジグザグ積およびUSTCONが対数領域で解けること2002,[論文 23] 2008[論文 24]
2010Sanjeev Arora, Joseph S. B. Mitchellユークリッド距離に基づく巡回セールスマン問題に対する多項式時間近似スキームの発見1998,[論文 25] 1999[論文 26]
2011Johan Håstadさまざまな組み合わせ問題に対する近似不可能性の証明2001[論文 27]
2012Elias Koutsoupias, クリストス・パパディミトリウ, Noam Nisan, Amir Ronen, Tim Roughgarden, Éva Tardosアルゴリズム的ゲーム理論の基礎を築く[1]2009,[論文 28] 2002,[論文 29] 2001[論文 30]
2013Dan 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]

2016Stephen Brookes, Peter O'HearnConcurrent Separation Logic の発明2007[論文 37], 2007[論文 38]
2017[5]Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam D. Smithdifferential privacyの発明2006[論文 39]
2018[6]Oded RegevLearning with errors問題の導入2009[論文 40]
2019[7]Irit DinurPCP定理に対する新たな証明2007[論文 41]
2020[8]Robin Moser, Gábor TardosLová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, http://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. 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”. (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日閲覧。
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.