- 哥德尔奖
哥德尔奖
中文名
哥德尔奖
时间
1993年
获奖名单
| 年份 | 姓名 | 理论成果 |
|---|---|---|
| 1993年 | László BabaiShafi GoldwasserSilvio MicaliShlomo MoranCharles 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 ImmermanRóbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity |
| 1996年 | Mark JerrumAlistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix |
| 1997年 | Maurice HerlihyMike SaksNir ShavitFotios 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. VardiPierre Wolper | for work on temporal logic with finite automata |
| 2001年 | Sanjeev AroraUriel FeigeShafi GoldwasserCarsten LundLászló LovászRajeev MotwaniShmuel SafraMadhu SudanMario 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 FreundRobert Schapire | for the AdaBoost algorithm in machine learning |
| 2004年 | Maurice HerlihyMike SaksNir ShavitFotios Zaharoglou | for applications of topology to the theory of distributed computing |
| 2005年 | Noga AlonYossi MatiasMario Szegedy | for their foundational contribution to streaming algorithms |
| 2006年 | Manindra AgrawalNeeraj KayalNitin Saxena | for the AKS primality test |
| 2007年 | Alexander RazborovSteven Rudich | for natural proofs |
| 2008年 | 滕尚华Daniel Spielman | for smoothed analysis of algorithms |
| 2009年 | Omer ReingoldSalil VadhanAvi Wigderson | for zig-zag product of graphs and undirected connectivity in log space |
| 2010年 | Sanjeev AroraJoseph 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 KoutsoupiasChristos PapadimitriouNoam NisanAmir RonenTim RoughgardenÉva Tardos | for laying the foundations of algorithmic game theory |
| 2013年 | Dan BonehMatthew K. FranklinAntoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography |
| 2014年 | Ronald FaginAmnon LotemMoni Naor | for Optimal Aggregation Algorithms for Middlewar |
| 2015年 | 滕尚华Daniel Spielman | for their series of papers on nearly-linear-time Laplacian solvers |
人物轶事
| 年份 | 姓名 | 理论成果 |
|---|---|---|
| 1993年 | László BabaiShafi GoldwasserSilvio MicaliShlomo MoranCharles 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 ImmermanRóbert Szelepcsényi | for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity |
| 1996年 | Mark JerrumAlistair Sinclair | for work on Markov chains and the approximation of the permanent of a matrix |
| 1997年 | Maurice HerlihyMike SaksNir ShavitFotios 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. VardiPierre Wolper | for work on temporal logic with finite automata |
| 2001年 | Sanjeev AroraUriel FeigeShafi GoldwasserCarsten LundLászló LovászRajeev MotwaniShmuel SafraMadhu SudanMario 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 FreundRobert Schapire | for the AdaBoost algorithm in machine learning |
| 2004年 | Maurice HerlihyMike SaksNir ShavitFotios Zaharoglou | for applications of topology to the theory of distributed computing |
| 2005年 | Noga AlonYossi MatiasMario Szegedy | for their foundational contribution to streaming algorithms |
| 2006年 | Manindra AgrawalNeeraj KayalNitin Saxena | for the AKS primality test |
| 2007年 | Alexander RazborovSteven Rudich | for natural proofs |
| 2008年 | 滕尚华Daniel Spielman | for smoothed analysis of algorithms |
| 2009年 | Omer ReingoldSalil VadhanAvi Wigderson | for zig-zag product of graphs and undirected connectivity in log space |
| 2010年 | Sanjeev AroraJoseph 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 KoutsoupiasChristos PapadimitriouNoam NisanAmir RonenTim RoughgardenÉva Tardos | for laying the foundations of algorithmic game theory |
| 2013年 | Dan BonehMatthew K. FranklinAntoine Joux | for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography |
| 2014年 | Ronald FaginAmnon LotemMoni Naor | for Optimal Aggregation Algorithms for Middlewar |
| 2015年 | 滕尚华Daniel Spielman | for their series of papers on nearly-linear-time Laplacian solvers |
相关百科
-
-
第88届奥斯卡金像奖
2025-01-11 00:51:33 查看详情 -
-
-
-
-
-
-
-
求购