哥德尔奖（Gödel Prize），由欧洲计算机学会（EATCS）与美国计算机学会基础理论专业组织（ACM SIGACT）于1993年共同设立，颁给理论计算机领域最杰出的学术论文。其名称取自伟大的逻辑学家库尔特·哥德尔（Kurt Gödel）。哥德尔也被认为是理论计算机的先驱。着名的P vs. NP问题，被发现是哥德尔在1956年写给冯·诺依曼（John von Neumann）的一封信中首次提到的。哥德尔奖是理论计算机领域最负盛名的奖项。
哥德尔奖自1993年起每年于该年度的STOC或ICALP上颁发一次，奖金为$5000。
基本介绍
- 中文名：哥德尔奖
- 外文名：Gödel Prize
- 时间：1993年
- 目的：颁给理论计算机领域最杰出的学术
历年获奖者名单
| 年份 | 姓名 | 理论成果 |
|---|---|---|
1993年 | László Babai Shafi Goldwasser Silvio Micali Shlomo Moran Charles Rackoff | for the development ofinteractive proof systems |
1994年 | Johan Håstad | for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). |
1995年 | Neil Immerman Róbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity |
1996年 | Mark Jerrum Alistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix |
1997年 | Maurice Herlihy Mike Saks Nir Shavit Fotios Zaharoglou | for defining a formal notion of "knowledge" in distributed environments |
1998年 | Seinosuke Toda | for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) |
1999年 | Peter Shor | for Shor's algorithm for factoring numbers in polynomial time on a quantum computer |
2000年 | Moshe Y. Vardi Pierre Wolper | for work on temporal logic with finite automata |
2001年 | Sanjeev Arora Uriel Feige Shafi Goldwasser Carsten Lund László Lovász Rajeev Motwani Shmuel Safra Madhu Sudan Mario Szegedy | for the PCP theorem and its applications to hardness of approximation |
2002年 | Géraud Sénizergues | for proving that equivalence of deterministic pushdown automata is decidable |
2003年 | Yoav Freund Robert Schapire | for the AdaBoost algorithm in machine learning |
2004年 | Maurice Herlihy Mike Saks Nir Shavit Fotios Zaharoglou | for applications of topology to the theory of distributed computing |
2005年 | Noga Alon Yossi Matias Mario Szegedy | for their foundational contribution to streaming algorithms |
2006年 | Manindra Agrawal Neeraj Kayal Nitin Saxena | for the AKS primality test |
2007年 | Alexander Razborov Steven Rudich | for natural proofs |
2008年 | 滕尚华 Daniel Spielman | for smoothed analysis of algorithms |
2009年 | Omer Reingold Salil Vadhan Avi Wigderson | for zig-zag product of graphs and undirected connectivity in log space |
2010年 | Sanjeev Arora Joseph S. B. Mitchell | for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) |
2011年 | Johan Håstad | for proving optimal inapproximability result for various combinatorial problems |
2012年 | Elias Koutsoupias Christos Papadimitriou Noam Nisan Amir Ronen Tim Roughgarden Éva Tardos | for laying the foundations of algorithmic game theory |
2013年 | Dan Boneh Matthew K. Franklin Antoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography |
2014年 | Ronald Fagin Amnon Lotem Moni Naor | for Optimal Aggregation Algorithms for Middlewar |
2015年 | 滕尚华 Daniel Spielman | for their series of papers on nearly-linear-time Laplacian solvers |
哥德尔奖轶事
1993年首届哥德尔奖得主中就有一位女性Shafi Goldwasser。Shafi Goldwasser与1993年另一位获奖者Silvio Micali于2012年共同获得图灵奖（Turing Award）。实际上，Shafi Goldwasser两次获得哥德尔奖，另一次是在2001年。截止到2015年，共有6位学者两次获奖，其他五位分别是Sanjeev Arora（2001,2010）和Johan Håstad（1994,2011）, 滕尚华和Daniel Spielman（2008,2015），Mario Szegedy（2001, 2005）。
截止到2015年，获奖的华人学者只有一位，是美国南加州大学滕尚华教授。
