Godel Prize
The Gödel Prize ( English Goedel Prize ) is since 1993 for outstanding publications in theoretical annual computer science from the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) awarded. It is endowed with 5000 dollars and is awarded at the STOC (Symposium on Theory of Computing) of the ACM in the USA or the corresponding European conference, the ICALP (International Colloquium on Automata, Languages and Programming). The work may not be older than 14 years (initially not older than 7 years).
The award is named after the important logician Kurt Gödel .
Award winners
- 1993 László Babai , Shafi Goldwasser , Silvio Micali , Shlomo Moran , Charles Rackoff (development of interactive evidence systems )
- 1994 Johan Håstad (exponential lower limit for the complexity of Boolean circuits of constant depth)
- 1995 Neil Immerman , Róbert Szelepcsényi ( Immerman and Szelepcsényi's theorem on nondeterministic space complexity)
- 1996 Mark Jerrum , Alistair Sinclair (work on Markov chains and approximation of the permanent )
- 1997 Joseph Halpern , Yoram Moses (formal definition of the term "knowledge" in distributed systems)
- 1998 Seinosuke Toda (for Toda's theorem in his work "PP is as Hard as the Polynomial-Time Hierarchy")
- 1999 Peter Shor (for his quantum computer algorithm for prime factorization )
- 2000 Moshe Y. Vardi , Pierre Wolper (Model Checking at Finite Machines)
- 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 )
- 2002 Géraud Sénizergues (proof of the decidability of the question of the equivalence of deterministic pushdown automata)
- 2003 Yoav Freund , Robert Schapire (AdaBoost Algorithm)
- 2004 Maurice Herlihy , Michael Saks , Nir Shavit , Fotios Zaharoglou (for applications of topology in the theory of computability in distributed systems)
- 2005 Noga Alon , Yossi Matias , Mario Szegedy (for fundamental contributions to data flow algorithms)
- 2006 Manindra Agrawal , Neeraj Kayal , Nitin Saxena (for their polynomial time prime test )
- 2007 Alexander Razborov , Steven Rudich (for their work "Natural Proofs")
- 2008 Shang-Hua Teng , Daniel Spielman ("smoothed analysis" of algorithms)
- 2009 Omer Reingold , Salil Vadhan , Avi Wigderson (zig-zag product of graphs)
- 2010 Sanjeev Arora , Joseph SB Mitchell (for a polynomial approximation scheme for the Euclidean traveling salesman problem)
- 2011 Johan Håstad (for the introduction of new analytical techniques in the theory of the difficulty of approximation in computational problems)
- 2012 Elias Koutsoupias and Christos Papadimitriou , Tim Roughgarden and Éva Tardos , Noam Nisan and Amir Ronen (each for a basic article on algorithmic game theory )
- 2013 Antoine Joux for A One Round Protocol for Tripartite Diffie-Hellman and Dan Boneh and Matthew K. Franklin for Identity-Based Encryption from the Weil Pairing
- 2014 Ronald Fagin , Amnon Lotem and Moni Naor for Optimal Aggregation Algorithms for Middleware
- 2015 Daniel A. Spielman and Shang-Hua Teng for nearly-linear-time Laplacian solvers
- 2016 Stephen Brookes and Peter W. O'Hearn for Concurrent Separation Logic
- 2017 Cynthia Dwork , Frank McSherry , Kobbi Nissim and Adam Smith for their essay Calibrating Noise to Sensitivity in Private Data Analysis
- 2018 Oded Regev for On lattices, learning with errors, random linear codes, and cryptography
- 2019 Irit Dinur for The PCP theorem by gap amplification
- 2020 Robin A. Moser , Gábor Tardos for A constructive proof of the general Lovász Local Lemma