哥德爾獎

哥德爾獎（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年，獲獎的華人學者只有一位，是美國南加州大學滕尚華教授。