哥德尔奖

哥德尔奖（Gödel Prize），由欧洲计算机学会（EATCS）与美国计算机学会基础理论专业组织（ACM SIGACT）于1993年共同设立，颁给理论计算机领域最杰出的学术论文。其名称取自伟大的逻辑学家库尔特·哥德尔（Kurt Gödel）。哥德尔也被认为是理论计算机的先驱。著名的P vs. NP问题，被发现是哥德尔在1956年写给冯·诺依曼（John von Neumann）的一封信中首次提到的。哥德尔奖是理论计算机领域最负盛名的奖项。

哥德尔奖自1993年起每年于该年度的STOC或ICALP上颁发一次，奖金为$5000。

年份姓名理论成果1993年László BabaiShafi GoldwasserSilvio MicaliShlomo MoranCharles Rackofffor the development ofinteractive proof systems1994年Johan Håstadfor an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).1995年Neil ImmermanRóbert Szelepcsényifor the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity1996年Mark JerrumAlistair Sinclairfor work on Markov chains and the approximation of the permanent of a matrix1997年Maurice HerlihyMike SaksNir ShavitFotios Zaharogloufor defining a formal notion of "knowledge" in distributed environments1998年Seinosuke Todafor Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)1999年Peter Shorfor Shor's algorithm for factoring numbers in polynomial time on a quantum computer2000年Moshe Y. VardiPierre Wolperfor work on temporal logic with finite automata2001年Sanjeev AroraUriel FeigeShafi GoldwasserCarsten LundLászló LovászRajeev MotwaniShmuel SafraMadhu SudanMario Szegedyfor the PCP theorem and its applications to hardness of approximation2002年Géraud Sénizerguesfor proving that equivalence of deterministic pushdown automata is decidable2003年Yoav FreundRobert Schapirefor the AdaBoost algorithm in machine learning2004年Maurice HerlihyMike SaksNir ShavitFotios Zaharogloufor applications of topology to the theory of distributed computing2005年Noga AlonYossi MatiasMario Szegedyfor their foundational contribution to streaming algorithms2006年Manindra AgrawalNeeraj KayalNitin Saxenafor the AKS primality test2007年Alexander RazborovSteven Rudichfor natural proofs2008年滕尚华Daniel Spielmanfor smoothed analysis of algorithms2009年Omer ReingoldSalil VadhanAvi Wigdersonfor zig-zag product of graphs and undirected connectivity in log space2010年Sanjeev AroraJoseph S. B. Mitchellfor their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP)2011年Johan Håstadfor proving optimal inapproximability result for various combinatorial problems2012年Elias KoutsoupiasChristos PapadimitriouNoam NisanAmir RonenTim RoughgardenÉva Tardosfor laying the foundations of algorithmic game theory2013年Dan BonehMatthew K. FranklinAntoine Jouxfor multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography2014年Ronald FaginAmnon LotemMoni Naorfor Optimal Aggregation Algorithms for Middlewar2015年滕尚华Daniel Spielmanfor 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年，获奖的华人学者只有一位，是美国南加州大学滕尚华教授。