哥德尔奖

维基百科，自由的百科全书

哥德尔奖（英语：Gödel Prize）是一个颁发给理论计算机科学领域杰出论文的年度奖项，由欧洲理论计算机科学协会（英语：European Association for Theoretical Computer Science）（EATCS）和美国计算机协会算法和计算理论特别兴趣小组（计算机协会算法和计算理论特别兴趣小组（英语：ACM SIGACT））联合颁发。该奖项是为纪念库尔特·哥德尔而命名的。哥德尔是第一个提出P/NP问题的人，在1956年写给约翰·冯·诺伊曼的信中，哥德尔问某个NP完全的问题是否可以用二次或是线性时间来解决[1]。

哥德尔奖于1993年开始在STOC（ACM计算理论研讨会（英语：Symposium on Theory of Computing），北美理论计算机科学的主要会议之一）或ICALP（自动机、语言和编程国际座谈会（英语：International Colloquium on Automata, Languages and Programming），该领域的主要欧洲会议之一）上颁发。获奖论文必须在理论计算机领域具有开创性重大贡献，同时需在获奖前14年内在学术期刊上正式发表。该奖项包括5,000美元的奖金[2]。

哥德尔奖的评审委员会由6名成员组成，分别由EATCS主席和SIGACT主席各提名三名成员，任期三年并交错进行。委员会由EATCS和SIGACT的代表轮流担任主席。

获奖者[编辑]

年份 获奖者 原因 发表时间
1993 拉斯洛·鲍鲍伊（英语：László Babai）、莎菲·戈德瓦塞尔、希尔维奥·米卡利、什洛莫·莫兰（英语：Shlomo Moran）、查尔斯·拉克福（英语：Charles Rackoff） 表彰其开发交互式证明系统 1988[paper 1]
1989[paper 2]
1994 约翰·哈斯塔德（英语：Johan Håstad） 表彰其证明恒深布林电路（英语：Boolean circuit）大小的指数下界（对于奇偶函数（英语：Parity function）） 1989[paper 3]
1995 尼尔·伊莫曼（英语：Neil Immerman）、罗伯特·塞莱普切尼（英语：Róbert Szelepcsényi） 表彰其证明非决定性空间复杂性的伊莫曼-塞莱普切尼定理（英语：Immerman–Szelepcsényi theorem） 1988[paper 4]
1988[paper 5]
1996 马克·杰鲁姆（英语：Mark Jerrum）、阿利斯泰尔·辛克莱尔 表彰其在马可夫链和矩阵积和式的近似方面的工作 1989[paper 6]
1989[paper 7]
1997 约瑟夫·哈尔彭（英语：Joseph Halpern）、约拉姆·莫塞斯（英语：Yoram Moses） 表彰其为分布式环境中的“知识”定义一个正式的概念 1990[paper 8]
1998 户田诚之助（日语：戸田誠之助） 表彰其证明显示计数解（PP）和量词交替（PH）之间的关联的户田定理 1991[paper 9]
1999 彼得·秀尔 表彰其开发在量子计算机上以多项式时间计算整数分解的秀尔算法 1997[paper 10]
2000 摩西·瓦迪（英语：Moshe Vardi）、皮埃尔·沃尔珀（英语：Pierre Wolper） 表彰其在有限状态机的时间逻辑方面的工作 1994[paper 11]
2001 桑吉夫·阿罗拉（英语：Sanjeev Arora）、乌列尔·费奇（英语：Uriel Feige）、莎菲·戈德瓦塞尔、卡斯坦·隆德（英语：Carsten Lund）、洛瓦兹·拉兹洛、拉耶夫·莫特瓦尼（英语：Rajeev Motwani）、什穆埃尔·沙夫拉（英语：Shmuel Safra）、迈度·苏丹（英语：Madhu Sudan）、马里奥·塞格德（英语：Mario Szegedy） 表彰其证明PCP定理（英语：PCP theorem）以及在近似硬度方面的应用 1996[paper 12]
1998[paper 13]
1998[paper 14]
2002 杰霍·赛尼泽格（英语：Géraud Sénizergues） 表彰其证明确定下推自动机的等价性是可决定（英语：Decidability (logic)）的 2001[paper 15]
2003 约阿夫·弗罗因德、罗伯特·沙皮尔 表彰其开发机器学习中的AdaBoost算法 1997[paper 16]
2004 莫里斯·赫利希（英语：Maurice Herlihy）、麦可·萨克斯（英语：Michael Saks (mathematician)）、尼尔·沙维特（英语：Nir Shavit）、弗蒂奥斯·札哈罗格罗（英语：Fotios Zaharoglou） 表彰其在拓扑学在分布式计算理论中的应用 1999[paper 17]
2000[paper 18]
2005 诺加·阿隆、约西·马蒂亚斯（英语：Yossi Matias）、马里奥·塞格德（英语：Mario Szegedy） 表彰其对Streaming algorithm（英语：串流演算法）的基础性贡献 1999[paper 19]
2006 曼宁德拉·阿格拉瓦尔（英语：Manindra Agrawal）、尼拉吉·卡亚尔（英语：Neeraj Kayal）、尼汀·沙克谢纳（英语：Nitin Saxena） 表彰其开发AKS质数测试 2004[paper 20]
2007 亚历山大·拉兹波洛夫（英语：Alexander Razborov）、史蒂芬·鲁迪奇（英语：Steven Rudich） 表彰其提出 自然证明（英语：Natural proof） 1997[paper 21]
2008 丹尼尔·斯皮尔曼（英语：Daniel Spielman）、滕尚华 表彰其开发算法的平滑分析（英语：Smoothed analysis） 2004[paper 22]
2009 奥马尔·莱因戈尔德（英语：Omer Reingold）、萨利尔·瓦德汉（英语：Salil Vadhan）、阿维·威格森 表彰其证明图的锯齿乘积（英语：Zig-zag product）和对数空间中的无定向连接性 2002[paper 23]
2008[paper 24]
2010 桑吉夫·阿罗拉（英语：Sanjeev Arora）、约瑟夫·S·B·米切尔（英语：Joseph S. B. Mitchell） 表彰其发现欧几里得旅行推销员问题（ETSP）的多项式时间近似算法（PTAS） 1998[paper 25]
1999[paper 26]
2011 约翰·哈斯塔德（英语：Johan Håstad） 表彰其证明各种组合问题的最佳非近似性结果 2001[paper 27]
2012 埃利亚斯·库特索皮亚斯（英语：Elias Koutsoupias）、赫里斯托斯·帕帕季米特里乌、诺姆·尼散、阿米尔·罗能（Amir Ronen）、提姆·罗加登（英语：Tim Roughgarden）、陶尔多什·埃娃 表彰其奠定算法博弈论（英语：Algorithmic game theory）的基础[3] 2009[paper 28]
2001[paper 29]
2002[paper 30]
2013 丹·博内、马修·K·富兰克林（英语：Matthew K. Franklin）、安托万·朱斯（英语：Antoine Joux） 表彰其开发多方迪菲-赫尔曼密钥交换和密码学中的博内-富兰克林法（英语：Boneh–Franklin scheme）[4] 2003[paper 31]
2004[paper 32]
2014 罗纳德·法金（英语：Ronald Fagin）、阿姆农·洛特姆（Amnon Lotem）、莫尼·瑙尔（英语：Moni Naor） 表彰其开发中介软体的最佳集合算法[5] 2003[paper 33]
2015 丹尼尔·斯皮尔曼（英语：Daniel Spielman）、滕尚华 表彰其开发近线性时间的拉普拉斯求解器[6] 2011[paper 34]
2013[paper 35]
2014[paper 36]
2016 史蒂芬·布鲁克斯（Stephen Brookes）、彼得·欧赫恩（英语：Peter O'Hearn） 表彰其开发并行分离逻辑（英语：Separation logic） 2007[paper 37]
2007[paper 38]
2017[2] 辛西娅·德沃克（英语：Cynthia Dwork）、弗兰克·麦克谢里（英语：Frank McSherry）、科比·尼西姆（英语：Kobbi Nissim）、亚当·D·史密斯（英语：Adam D. Smith） 表彰其开发差分隐私 2006[paper 39]
2018[7] 欧德德·瑞格夫（英语：Oded Regev (computer scientist)） 表彰其介绍容错学习问题 2009[paper 40]
2019[8] 伊里特·迪努尔（英语：Irit Dinur） 表彰其利用间隙放大法重新证明PCP定理（英语：PCP theorem） 2007[paper 41]
2020[9] 罗宾·莫瑟（Robin Moser）、陶尔多什·加博尔（英语：Gábor Tardos） 表彰其对拉兹洛局部定理（英语：Lovász local lemma）的建设性证明（英语：Algorithmic Lovász local lemma） 2010[paper 42]
2021[10] 安德烈·布拉托夫（Andrei Bulatov）、蔡进一（英语：Jin-Yi Cai）、陈汐（英语：Xi Chen）、马丁·戴尔（英语：Martin Dyer）、大卫·里切尔比（David Richerby） 表彰其在约束满足问题的计数复杂性（英语：Counting problem (complexity)）分类方面的工作 2013[paper 43]
2013[paper 44]
2017[paper 45]
2022[11] 兹维卡·布拉克斯基（Zvika Brakerski）、克雷格·金特里（英语：Craig Gentry (computer scientist)）、维诺德·维昆塔森（Vinod Vaikuntanathan） 表彰其通过构建高效的全同态加密（FHE）法对密码学的变革性贡献 2014[paper 46]
2014[paper 47]

获奖论文[编辑]

  1. ^ Babai, László; Moran, Shlomo, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class (PDF), Journal of Computer and System Sciences, 1988, 36 (2): 254–276 [2022-10-31], ISSN 0022-0000, doi:10.1016/0022-0000(88)90028-1 可免费查阅, （原始内容存档 (PDF)于2011-07-06） 
  2. ^ Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems (PDF), SIAM Journal on Computing, 1989, 18 (1): 186–208 [2022-10-31], CiteSeerX 10.1.1.397.4002 可免费查阅, ISSN 1095-7111, doi:10.1137/0218012, （原始内容存档 (PDF)于2011-09-27） 
  3. ^ Håstad, Johan, Almost Optimal Lower Bounds for Small Depth Circuits (PDF), Micali, Silvio (编), Randomness and Computation, Advances in Computing Research 5, JAI Press: 6–20, 1989, ISBN 978-0-89232-896-3, （原始内容 (PDF)存档于2012-02-22） 
  4. ^ Immerman, Neil, Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, 1988, 17 (5): 935–938 [2022-10-31], CiteSeerX 10.1.1.54.5941 可免费查阅, ISSN 1095-7111, doi:10.1137/0217058, （原始内容存档 (PDF)于2012-02-07） 
  5. ^ Szelepcsényi, R., The method of forced enumeration for nondeterministic automata (PDF), Acta Informatica, 1988, 26 (3): 279–284 [2022-10-31], S2CID 10838178, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489, （原始内容存档 (PDF)于2022-08-01） 
  6. ^ Sinclair, A.; Jerrum, M., Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, 1989, 82 (1): 93–133, ISSN 0890-5401, doi:10.1016/0890-5401(89)90067-9 
  7. ^ Jerrum, M.; Sinclair, Alistair, Approximating the permanent, SIAM Journal on Computing, 1989, 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 可免费查阅, ISSN 1095-7111, doi:10.1137/0218077 
  8. ^ Halpern, Joseph; Moses, Yoram, Knowledge and common knowledge in a distributed environment (PDF), Journal of the ACM, 1990, 37 (3): 549–587 [2022-10-31], S2CID 52151232, arXiv:cs/0006009 可免费查阅, doi:10.1145/79147.79161, （原始内容存档 (PDF)于2019-02-02） 
  9. ^ Toda, Seinosuke, PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing, 1991, 20 (5): 865–877 [2022-10-31], CiteSeerX 10.1.1.121.1246 可免费查阅, ISSN 1095-7111, doi:10.1137/0220053, （原始内容 (PDF)存档于2016-03-03） 
  10. ^ Shor, Peter W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, 1997, 26 (5): 1484–1509, ISSN 1095-7111, S2CID 2337707, arXiv:quant-ph/9508027 可免费查阅, doi:10.1137/S0097539795293172 
  11. ^ Vardi, Moshe Y.; Wolper, Pierre, Reasoning about infinite computations (PDF), Information and Computation, 1994, 115 (1): 1–37, ISSN 0890-5401, doi:10.1006/inco.1994.1092, （原始内容 (PDF)存档于2011-08-25） 
  12. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario, Interactive proofs and the hardness of approximating cliques (PDF), Journal of the ACM, 1996, 43 (2): 268–292 [2022-10-31], ISSN 0004-5411, doi:10.1145/226643.226652 可免费查阅, （原始内容存档 (PDF)于2011-06-10） 
  13. ^ Arora, Sanjeev; Safra, Shmuel, Probabilistic checking of proofs: a new characterization of NP (PDF), Journal of the ACM, 1998, 45 (1): 70–122, ISSN 0004-5411, S2CID 751563, doi:10.1145/273865.273901, （原始内容 (PDF)存档于2011-06-10） 
  14. ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario, Proof verification and the hardness of approximation problems (PDF), Journal of the ACM, 1998, 45 (3): 501–555, CiteSeerX 10.1.1.145.4652 可免费查阅, ISSN 0004-5411, S2CID 8561542, doi:10.1145/278298.278306, （原始内容 (PDF)存档于2011-06-10） 
  15. ^ Sénizergues, Géraud, L(A) = L(B)? decidability results from complete formal systems, Theor. Comput. Sci., 2001, 251 (1): 1–166, ISSN 0304-3975, doi:10.1016/S0304-3975(00)00285-1 可免费查阅 
  16. ^ Freund, Y.; Schapire, R.E., A decision-theoretic generalization of on-line learning and an application to boosting (PDF), Journal of Computer and System Sciences, 1997, 55 (1): 119–139 [2022-10-31], ISSN 1090-2724, doi:10.1006/jcss.1997.1504, （原始内容存档 (PDF)于2011-07-19） 
  17. ^ Herlihy, Maurice; Shavit, Nir, The topological structure of asynchronous computability (PDF), Journal of the ACM, 1999, 46 (6): 858–923 [2022-10-31], CiteSeerX 10.1.1.78.1455 可免费查阅, S2CID 5797174, doi:10.1145/331524.331529, （原始内容存档 (PDF)于2011-06-05） . Gödel prize lecture （页面存档备份，存于互联网档案馆）
  18. ^ Saks, Michael; Zaharoglou, Fotios, Wait-free k-set agreement is impossible: The topology of public knowledge, SIAM Journal on Computing, 2000, 29 (5): 1449–1483, doi:10.1137/S0097539796307698 
  19. ^ Alon, Noga; Matias, Yossi; Szegedy, Mario, The space complexity of approximating the frequency moments (PDF), Journal of Computer and System Sciences, 1999, 58 (1): 137–147, doi:10.1006/jcss.1997.1545 . First presented at the Symposium on Theory of Computing (STOC) in 1996.
  20. ^ Agrawal, M.; Kayal, N.; Saxena, N., PRIMES is in P, Annals of Mathematics, 2004, 160 (2): 781–793, ISSN 0003-486X, doi:10.4007/annals.2004.160.781 可免费查阅 
  21. ^ Razborov, Alexander A.; Rudich, Steven, Natural proofs, Journal of Computer and System Sciences, 1997, 55 (1): 24–35, ISSN 0022-0000, doi:10.1006/jcss.1997.1494 可免费查阅 
  22. ^ Spielman, Daniel A.; Teng, Shang-Hua, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM, 2004, 51 (3): 385–463, ISSN 0004-5411, arXiv:math/0212413 可免费查阅, doi:10.1145/990308.990310 
  23. ^ Reingold, Omer; Vadhan, Salil; Wigderson, Avi, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics, 2002, 155 (1): 157–187, CiteSeerX 10.1.1.236.8669 可免费查阅, ISSN 0003-486X, JSTOR 3062153, MR 1888797, S2CID 120739405, doi:10.2307/3062153 
  24. ^ Reingold, Omer, Undirected connectivity in log-space, J. ACM, 2008, 55 (4): 1–24 [2022-10-31], ISSN 0004-5411, S2CID 207168478, doi:10.1145/1391289.1391291, （原始内容存档于2011-06-12） 
  25. ^ Arora, Sanjeev, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, 1998, 45 (5): 753–782, CiteSeerX 10.1.1.23.6765 可免费查阅, ISSN 0004-5411, S2CID 3023351, doi:10.1145/290179.290180 
  26. ^ Mitchell, Joseph S. B., Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, 1999, 28 (4): 1298–1309, ISSN 1095-7111, doi:10.1137/S0097539796309764 
  27. ^ Håstad, Johan, Some optimal inapproximability results (PDF), Journal of the ACM, 2001, 48 (4): 798–859 [2022-10-31], CiteSeerX 10.1.1.638.2808 可免费查阅, ISSN 0004-5411, S2CID 5120748, doi:10.1145/502090.502098, （原始内容存档 (PDF)于2012-03-12） 
  28. ^ Koutsoupias, Elias; Papadimitriou, Christos. Worst-case equilibria. Computer Science Review. 2009, 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003. 
  29. ^ Nisan, Noam; Ronen, Amir. Algorithmic Mechanism Design. Games and Economic Behavior. 2001, 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 可免费查阅. doi:10.1006/game.1999.0790. 
  30. ^ Roughgarden, Tim; Tardos, Éva. How bad is selfish routing?. Journal of the ACM. 2002, 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 可免费查阅. S2CID 207638789. doi:10.1145/506147.506153. 
  31. ^ Boneh, Dan; Franklin, Matthew. Identity-based encryption from the Weil pairing. SIAM Journal on Computing. 2003, 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 可免费查阅. MR 2001745. doi:10.1137/S0097539701398521. 
  32. ^ Joux, Antoine. A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology. 2004, 17 (4): 263–276. MR 2090557. S2CID 3350730. doi:10.1007/s00145-004-0312-y. 
  33. ^ Fagin, Ronald; Lotem, Amnon; Naor, Moni. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences. 2003, 66 (4): 614–656. arXiv:cs/0204046 可免费查阅. doi:10.1016/S0022-0000(03)00026-6. 
  34. ^ Spielman, Daniel A.; Teng, Shang-Hua. Spectral Sparsification of Graphs. SIAM Journal on Computing. 2011, 40 (4): 981–1025. ISSN 0097-5397. S2CID 9646279. arXiv:0808.4134 可免费查阅. doi:10.1137/08074489X. 
  35. ^ Spielman, Daniel A.; Teng, Shang-Hua. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on Computing. 2013, 42 (1): 1–26. ISSN 0097-5397. S2CID 9151077. arXiv:0809.3232 可免费查阅. doi:10.1137/080744888. 
  36. ^ Spielman, Daniel A.; Teng, Shang-Hua. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis and Applications. 2014, 35 (3): 835–885. ISSN 0895-4798. S2CID 1750944. arXiv:cs/0607105 可免费查阅. doi:10.1137/090771430. 
  37. ^ Brookes, Stephen. A Semantics for Concurrent Separation Logic (PDF). Theoretical Computer Science. 2007, 375 (1–3): 227–270 [2022-10-31]. doi:10.1016/j.tcs.2006.12.034. （原始内容存档 (PDF)于2021-05-09）. 
  38. ^ O'Hearn, Peter. Resources, Concurrency and Local Reasoning (PDF). Theoretical Computer Science. 2007, 375 (1–3): 271–307 [2022-10-31]. doi:10.1016/j.tcs.2006.12.035 可免费查阅. （原始内容存档 (PDF)于2021-03-04）. 
  39. ^ Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam. Halevi, Shai; Rabin, Tal , 编. Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science 3876. Springer-Verlag: 265–284. 2006. ISBN 978-3-540-32731-8. doi:10.1007/11681878_14 可免费查阅. 
  40. ^ Regev, Oded. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM. 2009, 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 可免费查阅. S2CID 207156623. doi:10.1145/1568318.1568324. 
  41. ^ Dinur, Irit. The PCP theorem by gap amplification. Journal of the ACM. 2007, 54 (3): 12–es. S2CID 53244523. doi:10.1145/1236457.1236459. 
  42. ^ A constructive proof of the general Lovász Local Lemma. Journal of the ACM. 2010, 57 (2). ISSN 0004-5411. doi:10.1145/1667053. 
  43. ^ Bulatov, Andrei A. The complexity of the counting constraint satisfaction problem. Journal of the ACM (Association for Computing Machinery (ACM)). 2013, 60 (5): 1–41. ISSN 0004-5411. S2CID 8964233. doi:10.1145/2528400. 
  44. ^ Dyer, Martin; Richerby, David. An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM Journal on Computing (Society for Industrial & Applied Mathematics (SIAM)). 2013, 42 (3): 1245–1274. ISSN 0097-5397. S2CID 1247279. arXiv:1003.3879 可免费查阅. doi:10.1137/100811258. 
  45. ^ Cai, Jin-Yi; Chen, Xi. Complexity of Counting CSP with Complex Weights. Journal of the ACM (Association for Computing Machinery (ACM)). 2017-06-22, 64 (3): 1–39. ISSN 0004-5411. S2CID 1053684. arXiv:1111.2384 可免费查阅. doi:10.1145/2822891. 
  46. ^ Brakerski, Zvika; Vaikuntanathan, Vinod. Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. SIAM Journal on Computing. January 2014, 43 (2): 831–871. ISSN 0097-5397. doi:10.1137/120868669. 
  47. ^ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod. (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). 2012. doi:10.1145/2090236.2090262. 

参考文献[编辑]

  1. ^ The Gödel Letter. 2009-02-12 [2022-10-31]. （原始内容存档于2019-01-30）. 
  2. ^ 2.0 2.1 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. [29 March 2017]. （原始内容存档于2019-04-16）. 
  3. ^ Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012 [16 May 2012]. （原始内容存档于18 July 2013）. 
  4. ^ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security 互联网档案馆的存档，存档日期2013-06-01., Association for Computing Machinery, May 29, 2013.
  5. ^ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources （页面存档备份，存于互联网档案馆）, Association for Computing Machinery, April 30, 2014.
  6. ^ 2015 Gödel Prize announcement 互联网档案馆的存档，存档日期2017-12-09. by Association for Computing Machinery.
  7. ^ 2018 Gödel Prize citation. [2020-05-17]. （原始内容存档于2018-10-05）. 
  8. ^ 2019 Gödel Prize citation. [2020-05-17]. （原始内容存档于2020-07-28）. 
  9. ^ 2020 Gödel Prize citation. [2020-05-17]. （原始内容存档于2020-07-16）. 
  10. ^ 2021 Gödel Prize citation. [2022-10-31]. （原始内容存档于2022-06-04）. 
  11. ^ 2022 Gödel Prize citation. [2022-10-31]. （原始内容存档于2022-10-31）. 
哥德尔奖获得者
1990年代

1993年：鲍鲍伊（英语：László Babai）、戈德瓦塞尔、米卡利、莫兰（英语：Shlomo Moran）、拉克福（英语：Charles Rackoff） / 1994年：哈斯塔德（英语：Johan Håstad） / 1995年：伊莫曼（英语：Neil Immerman）、塞莱普切尼（英语：Róbert Szelepcsényi） / 1996年：杰鲁姆（英语：Mark Jerrum）、辛克莱尔 / 1997年：哈尔彭（英语：Joseph Halpern）、莫塞斯（英语：Yoram Moses） / 1998年：户田诚之助（日语：戸田誠之助） / 1999年：秀尔

2000年代

2000年：瓦迪（英语：Moshe Vardi）、沃尔珀（英语：Pierre Wolper） / 2001年：阿罗拉（英语：Sanjeev Arora）、费奇（英语：Uriel Feige）、戈德瓦塞尔、隆德（英语：Carsten Lund）、拉斯洛、莫特瓦尼（英语：Rajeev Motwani）、沙夫拉（英语：Shmuel Safra）、苏丹（英语：Madhu Sudan）、塞格德（英语：Mario Szegedy） / 2002年：赛尼泽格（英语：Géraud Sénizergues） / 2003年：弗罗因德、沙皮尔 / 2004年：赫利希（英语：Maurice Herlihy）、萨克斯（英语：Michael Saks (mathematician)）、沙维特（英语：Nir Shavit）和札哈罗格罗（英语：Fotios Zaharoglou） / 2005年：阿隆、马蒂亚斯（英语：Yossi Matias）、塞格德（英语：Mario Szegedy） / 2006年：阿格拉瓦尔（英语：Manindra Agrawal）、卡亚尔（英语：Neeraj Kayal）、沙克谢纳（英语：Nitin Saxena） / 2007年：拉兹波洛夫（英语：Alexander Razborov）、鲁迪奇（英语：Steven Rudich） / 2008年：斯皮尔曼（英语：Daniel Spielman）、滕尚华 / 2009年：莱因戈尔德（英语：Omer Reingold）、瓦德汉（英语：Salil Vadhan）、威格德森

2010年代

2010年：阿罗拉（英语：Sanjeev Arora）、米切尔（英语：Joseph S. B. Mitchell） / 2011年：哈斯塔德（英语：Johan Håstad） / 2012年：库特索皮亚斯（英语：Elias Koutsoupias）、帕帕季米特里乌、尼散、罗能、罗加登（英语：Tim Roughgarden）、陶尔多什·É / 2013年：博内、富兰克林（英语：Matthew K. Franklin）、朱斯（英语：Antoine Joux） / 2014年：法金（英语：Ronald Fagin）、洛特姆、瑙尔（英语：Moni Naor） / 2015年：斯皮尔曼（英语：Daniel Spielman）、滕尚华 / 2016年：布鲁克斯、欧赫恩（英语：Peter O'Hearn） / 2017年：德沃克（英语：Cynthia Dwork）、麦克谢里（英语：Frank McSherry）、尼西姆（英语：Kobbi Nissim）、史密斯（英语：Adam D. Smith） / 2018年：瑞格夫（英语：Oded Regev (computer scientist)） / 2019年：迪努尔（英语：Irit Dinur）

2020年代

2020年：莫瑟、陶尔多什·G（英语：Gábor Tardos） / 2021年：布拉托夫、蔡进一（英语：Jin-Yi Cai）、陈汐（英语：Xi Chen）、戴尔（英语：Martin Dyer）、里切尔比 / 2022年：布拉克斯基、金特里（英语：Craig Gentry (computer scientist)）、维昆塔森

取自“https://zh.wikipedia.org/w/index.php?title=哥德尔奖&oldid=76409769”