哥德爾獎

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

相關詞條

熱門詞條

聯絡我們