哥德尔奖
科学奖励 / 维基百科,自由的 encyclopedia
哥德尔奖(英语: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的代表轮流担任主席。
获奖者
More information 年份, 获奖者 ...
年份 | 获奖者 | 原因 | 发表时间 |
---|---|---|---|
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] |
Close
获奖论文
- 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)
- 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)
- 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)
- 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)
- 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)
- 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
- 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
- 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)
- 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)
- 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
- 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)
- 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)
- 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)
- 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)
- 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
- 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)
- 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 (页面存档备份,存于互联网档案馆)
- 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
- 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.
- 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
- 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
- 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
- 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
- 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)
- 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
- 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
- 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)
- Koutsoupias, Elias; Papadimitriou, Christos. Worst-case equilibria. Computer Science Review. 2009, 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
- 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).
- 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
.
- 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.
- Dinur, Irit. The PCP theorem by gap amplification. Journal of the ACM. 2007, 54 (3): 12–es. S2CID 53244523. doi:10.1145/1236457.1236459.
- A constructive proof of the general Lovász Local Lemma. Journal of the ACM. 2010, 57 (2). ISSN 0004-5411. doi:10.1145/1667053.
- 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.
- 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.
- 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.
- 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.
- 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.
参考文献
- The Gödel Letter. 2009-02-12 [2022-10-31]. (原始内容存档于2019-01-30).
- 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. [29 March 2017]. (原始内容存档于2019-04-16).
- Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012 [16 May 2012]. (原始内容存档于18 July 2013).
- 2015 Gödel Prize announcement 互联网档案馆的存档,存档日期2017-12-09. by Association for Computing Machinery.
- 2018 Gödel Prize citation. [2020-05-17]. (原始内容存档于2018-10-05).
- 2019 Gödel Prize citation. [2020-05-17]. (原始内容存档于2020-07-28).
- 2020 Gödel Prize citation. [2020-05-17]. (原始内容存档于2020-07-16).
- 2021 Gödel Prize citation. [2022-10-31]. (原始内容存档于2022-06-04).
- 2022 Gödel Prize citation. [2022-10-31]. (原始内容存档于2022-10-31).