哥德尔奖

哥德尔奖（英语：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]
2023[12]	塞缪尔·费奥里尼（Samuel Fiorini）、塞尔日·马萨尔（英语：Serge Massar）、塞巴斯蒂安·波库塔（Sebastian Pokutta）、汉斯·拉吉·提瓦利（Hans Raj Tiwary）、隆纳·德·沃尔夫（英语：Ronald de Wolf）、托马斯·罗斯沃斯（Thomas Rothvoss）	表彰其透过建构高效率的完全同态加密（FHE）方案，对密码学所做的转变性贡献	2015,[paper 48]2017[paper 49]
2024[13]	莱恩·威廉斯（英语：Ryan Williams (computer scientist)）	表彰他在电路下界和“下界算法”范例方面的工作	2011[paper 50]
2025[14]	艾尚·查托帕迪亚伊（Eshan Chattopadhyay）、大卫·祖克曼（英语：David Zuckerman (computer scientist)）	以表彰其建构“具备多对数最小熵的显式双源萃取器，解决了计算理论中一个已存在将近三十年的核心问题”	2016[paper 51]