基本介紹
- 中文名:哥德爾獎
- 外文名: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年,獲獎的華人學者只有一位,是美國南加州大學滕尚華教授。