芒果视频下载

哥德(de)爾(er)獎（G?del Prize），由歐(ou)洲計(ji)(ji)算(suan)機學(xue)(xue)會（EATCS）與(yu)美國(guo)計(ji)(ji)算(suan)機學(xue)(xue)會基礎理論(lun)專業組織（ACM SIGACT）于(yu)1993年共同設(she)立，頒給(gei)理論(lun)計(ji)(ji)算(suan)機領(ling)域(yu)最杰出的(de)學(xue)(xue)術論(lun)文。其名稱取自偉大的(de)邏輯學(xue)(xue)家(jia)庫(ku)爾(er)特(te)·哥德(de)爾(er)（Kurt G?del）。哥德(de)爾(er)也被認為是(shi)理論(lun)計(ji)(ji)算(suan)機的(de)先驅。著(zhu)名的(de)P vs.NP問(wen)題，被發現是(shi)哥德(de)爾(er)在(zai)1956年寫給(gei)馮(feng)·諾(nuo)依曼(man)（John von Neumann）的(de)一封信(xin)中首(shou)次提到的(de)。哥德(de)爾(er)獎是(shi)理論(lun)計(ji)(ji)算(suan)機領(ling)域(yu)最負盛名的(de)獎項。

哥(ge)德爾獎(jiang)(jiang)自1993年(nian)(nian)起每年(nian)(nian)于(yu)該(gai)年(nian)(nian)度的(de)STOC或ICALP上頒(ban)發(fa)一次，獎(jiang)(jiang)金為$5000。

獲獎名單

年(nian)份(fen) 姓(xing)名 理論成果

1993年 László Babai for the development ofinteractive proof systems

Shafi Goldwasser

Silvio Micali

Shlomo Moran

Charles Rackoff

1994年 Johan H?stad for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).

1995年 Neil Immerman for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity

Róbert Szelepcsényi

1996年 Mark Jerrum for work on Markov chains and the approximation of the permanent of a matrix

Alistair Sinclair

1997年 Maurice Herlihy for defining a formal notion of "knowledge" in distributed environments

Mike Saks

Nir Shavit

Fotios Zaharoglou

1998年 Seinosuke Toda for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)

1999年(nian) Peter Shor for Shor's algorithm for factoring numbers in polynomial time on a quantum computer

2000年 Moshe Y. Vardi for work on temporal logic with finite automata

Pierre Wolper

2001年 Sanjeev Arora for the PCP theorem and its applications to hardness of approximation

Uriel Feige

Shafi Goldwasser

Carsten Lund

László Lovász

Rajeev Motwani

Shmuel Safra

Madhu Sudan

Mario Szegedy

2002年 Géraud Sénizergues for proving that equivalence of deterministic pushdown automata is decidable

2003年 Yoav Freund for the AdaBoost algorithm in machine learning

Robert Schapire

2004年 Maurice Herlihy for applications of topology to the theory of distributed computing

Mike Saks

Nir Shavit

Fotios Zaharoglou

2005年 Noga Alon for their foundational contribution to streaming algorithms

Yossi Matias

Mario Szegedy

2006年 Manindra Agrawal for the AKS primality test

Neeraj Kayal

Nitin Saxena

2007年 Alexander Razborov for natural proofs

Steven Rudich

2008年 滕(teng)尚華 for smoothed analysis of algorithms

Daniel Spielman

2009年 Omer Reingold for zig-zag product of graphs and undirected connectivity in log space

Salil Vadhan

Avi Wigderson

2010年 Sanjeev Arora for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP)

Joseph S. B. Mitchell

2011年(nian) Johan H?stad for proving optimal inapproximability result for various combinatorial problems

2012年 Elias Koutsoupias for laying the foundations of algorithmic game theory

Christos Papadimitriou

Noam Nisan

Amir Ronen

Tim Roughgarden

éva Tardos

2013年 Dan Boneh for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography

Matthew K. Franklin

Antoine Joux

2014年 Ronald Fagin for Optimal Aggregation Algorithms for Middlewar

Amnon Lotem

Moni Naor

2015年 滕尚華(hua) for their series of papers on nearly-linear-time Laplacian solvers

Daniel Spielman

人物軼事

1993年(nian)(nian)(nian)(nian)首屆哥德爾獎(jiang)(jiang)得(de)(de)主中就有(you)一(yi)位(wei)女(nv)性Shafi Goldwasser。Shafi Goldwasser與1993年(nian)(nian)(nian)(nian)另(ling)一(yi)位(wei)獲獎(jiang)(jiang)者Silvio Micali于2012年(nian)(nian)(nian)(nian)共(gong)同獲得(de)(de)圖靈(ling)獎(jiang)(jiang)（Turing Award）。實際上(shang)，Shafi Goldwasser兩次獲得(de)(de)哥德爾獎(jiang)(jiang)，另(ling)一(yi)次是在(zai)2001年(nian)(nian)(nian)(nian)。截止到2015年(nian)(nian)(nian)(nian)，共(gong)有(you)6位(wei)學者兩次獲獎(jiang)(jiang)，其他五位(wei)分別是Sanjeev Arora（2001,2010）和Johan H?stad（1994,2011）,滕尚華和Daniel Spielman（2008,2015），Mario Szegedy（2001, 2005）。

截(jie)止到2015年(nian)，獲(huo)獎的(de)華(hua)人學(xue)者只有一位(wei)，是美(mei)國南加州大學(xue)滕尚華(hua)教(jiao)授(shou)。