Gödel-Preis
Der Gödel-Preis wird jährlich seit 1993 für herausragende Veröffentlichungen in der theoretischen Informatik von der European Association for Theoretical Computer Science (EATCS) und der Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) verliehen. Er ist mit 5000 Dollar dotiert und wird auf der STOC (Symposium on Theory of Computing) der ACM in den USA oder der entsprechenden europäischen Konferenz, der ICALP (International Colloquium on Automata, Languages and Programming) verliehen. Die Arbeit darf nicht älter als 14 Jahre sein (anfangs sogar nicht älter als 7 Jahre).
Der Preis ist nach dem bedeutenden Logiker Kurt Gödel benannt.
Preisträger
- 1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, Charles Rackoff (Entwicklung von Interaktiven Beweissystemen)
- 1994 Johan Håstad (exponentielle untere Grenze für die Komplexität Boolescher Schaltkreise konstanter Tiefe)
- 1995 Neil Immerman, Róbert Szelepcsényi (Satz von Immerman und Szelepcsényi über nichtdeterministische Platzkomplexität)
- 1996 Mark Jerrum, Alistair Sinclair (Arbeit über Markow-Ketten und Approximation der Permanente)
- 1997 Joseph Halpern, Yoram Moses (formale Definition des Begriffs „Wissen“ in verteilten Systemen)
- 1998 Seinosuke Toda (für Todas Theorem in seiner Arbeit „PP is as Hard as the Polynomial-Time Hierarchy“)
- 1999 Peter Shor (für seinen Quantencomputer-Algorithmus zur Primfaktorzerlegung)
- 2000 Moshe Y. Vardi, Pierre Wolper (Model Checking bei Endlichen Automaten)
- 2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy (für das PCP-Theorem)
- 2002 Géraud Sénizergues (Beweis der Entscheidbarkeit der Frage der Äquivalenz deterministischer Pushdown-Automaten)
- 2003 Yoav Freund, Robert Schapire (AdaBoost Algorithmus)
- 2004 Maurice Herlihy, Michael Saks, Nir Shavit, Fotios Zaharoglou (für Anwendungen der Topologie in Theorie der Berechenbarkeit in verteilten Systemen)
- 2005 Noga Alon, Yossi Matias, Mario Szegedy (für fundamentale Beiträge zu Datenstrom-Algorithmen)
- 2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena (für ihren Polynomialzeit-Primzahltest)
- 2007 Alexander Razborov, Steven Rudich (für ihre Arbeit „Natural Proofs“)
- 2008 Shang-Hua Teng, Daniel Spielman („smoothed analysis“ von Algorithmen)
- 2009 Omer Reingold, Salil Vadhan, Avi Wigderson (zig-zag Produkt von Graphen)
- 2010 Sanjeev Arora, Joseph S. B. Mitchell (für Polynomialzeit-Approximationsalgorithmus der Lösung des euklidischen Handlungsreisenden-Problems)
- 2011 Johan Håstad (für die Einführung neuer analytischer Techniken in die Theorie der Schwierigkeit der Approximation bei Berechnungsproblemen)
- 2012 Elias Koutsoupias und Christos Papadimitriou, Tim Roughgarden und Éva Tardos, Noam Nisan und Amir Ronen (jeweils für einen grundlegenden Artikel zur Algorithmischen Spieltheorie)
- 2013 Antoine Joux für A One Round Protocol for Tripartite Diffie-Hellman und Dan Boneh und Matthew K. Franklin für Identity-Based Encryption from the Weil Pairing
- 2014 Ronald Fagin, Amnon Lotem und Moni Naor für Optimal Aggregation Algorithms for Middleware
- 2015 Daniel A. Spielman und Shang-Hua Teng für nearly-linear-time Laplacian solvers
- 2016 Stephen Brookes und Peter W. O’Hearn für Concurrent Separation Logic[1]
Weblinks
Einzelnachweise
- ↑ 2016 Godel Prize Recognizes Major Advances in Verification of Concurrent Programs. In: acm.org. 9. Mai 2016, abgerufen am 14. Mai 2016 (englisch).