Gödel-Preis

Der Gödel-Preis (englisch Goedel Prize) 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 ein polynomielles Approximationsschema für das euklidische Handlungsreisenden-Problem)
• 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
• 2017 Cynthia Dwork, Frank McSherry, Kobbi Nissim und Adam Davison Smith für ihren Aufsatz Calibrating Noise to Sensitivity in Private Data Analysis zu Differential Privacy
• 2018 Oded Regev für On lattices, learning with errors, random linear codes, and cryptography (gitterbasierte Kryptographie, Learning with errors)
• 2019 Irit Dinur für The PCP theorem by gap amplification (PCP-Theorem)
• 2020 Robin A. Moser, Gábor Tardos für A constructive proof of the general Lovász Local Lemma (konstruktive, algorithmische Version des Lovász-Local-Lemma)
• 2021 Andrei Bulatov für The Complexity of the Counting Constraint Satisfaction Problem, Martin E. Dyer, David Richerby für An Effective Dichotomy for the Counting Constraint Satisfaction Problem, Jin-Yi Cai, Xi Chen für Complexity of Counting CSP with Complex Weights, Abzähl-Constraint Satisfaction Problem
• 2022 Zvika Brakerski, Vinod Vaikuntanathan für Efficient Fully Homomorphic Encryption from (Standard) LWE, Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: (Leveled) fully homomorphic encryption without bootstrapping, homomorphe Verschlüsselung
• 2023: Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf für Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Thomas Rothvoss für The matching polytope has exponential extension complexity
• 2024: Ryan Williams für Non-Uniform ACC Circuit Lower Bounds

Weblinks

• Offizielle Webseite bei der ACM SIGACT
• Offizielle Webseite bei der EATCS