El Premio Gödel es un premio que se entrega a autores de artículos científicos destacados en teoría de la computación. Es otorgado por la European Association for Theoretical Computer Science (EATCS) y el Grupo de Interés Especial de Algoritmos y Teoría de la Computación de la Association for Computing Machinery (ACM SIGACT). Su nombre se debe al matemático Kurt Gödel, quien en una carta de 1956 dirigida a John von Neumann planteó por primera vez el problema de P vs NP.
El premio se entrega anualmente desde 1993, intercaladamente tanto en el EATCS International Colloquium on Automata, Languages, and Programming (ICALP) como en el ACM Symposium on Theory of Computing (STOC), dos importantes congresos en el área. Los artículos nominados deben haber sido publicados hace máximo 14 años atrás (anteriormente eran sólo 7 años). Además de la distinción, incluye un aporte de 5000 dólares.
Ganadores Los distintos ganadores del premio han sido los siguientes: Versión Autores Razón Añopublicación1993László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran y Charles RackoffPor el desarrollo de sistemas de demostración interactivos.198819891994Johan HåstadPor encontrar una cota inferior exponencial en función del tamaño de profundidad constante de un circuito booleano para la función paridad.19891995Neil Immerman y Róbert SzelepcsényiPor el Teorema de Immerman-Szelepcsényi, sobre complejidad espacial no-determinista.198819881996Mark Jerrum y Alistair SinclairPor sus trabajos sobre cadenas de Márkov y la aproximación del permanente de una matriz.198919891997Joseph Halpern y Yoram MosesPor definir una noción formal de «conocimiento» en entornos distribuidos.19901998Seinosuke TodaPor el Teorema de Toda, que demuestra una conexión entre contar soluciones (PP) y alternar cuantificadores (PH).19911999Peter ShorPor el algoritmo de Shor para factorizar números en tiempo polinómico en un computador cuántico.19972000Moshe Y. Vardi y Pierre WolperPor su aporte en lógica temporal con autómatas finitos.19942001Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan y Mario SzegedyPor el teorema PCP y sus aplicaciones a la dificultad de la aproximación.1996199819982002Géraud SénizerguesPor demostrar que la equivalencia de autómatas de pila deterministas es decidible.20012003Yoav Freund y Robert SchapirePor el algoritmo AdaBoost.19972004Maurice Herlihy, Mike Saks, Nir Shavit y Fotios ZaharoglouPor aplicar topología a la teoría de computación distribuida.1999. Gödel prize lecture20002005Noga Alon, Yossi Matias y Mario SzegedyPor su contribución fundacional a los algoritmos de streaming1999. First presented at the Symposium on Theory of Computing (STOC) in 1996.2006Manindra Agrawal, Neeraj Kayal, Nitin SaxenaPor el test de primalidad AKS20042007Alexander Razborov y Steven RudichPor las demostraciones naturales19972008Shanghua Teng y Daniel SpielmanPor el análisis smoothed de algoritmos20042009Omer Reingold, Avi Wigderson y Salil Vadhan200220082010Sanjeev Arora y Joseph S. B. Mitchell199819992011Johan Håstad20012012Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden y Éva Tardos2009200220012013Dan Boneh, Matthew K. Franklin y Antoine Joux200320042014Ronald Fagin, Amnon Lotem y Moni Naor20032015Daniel A. Spielman y Shang-Hua Teng2011201320142016Stephen Brookes y Peter W. O'Hearn200720072017Cynthia Dwork, Frank McSherry, Kobbi Nissim y Adam D. Smith20062018Oded Regev20092019Irit Dinur20072020Robin Moser y Gábor Tardos20102021Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer y David Richerby2013201320172022Zvika Brakerski, Craig Gentry y Vinod Vaikuntanathan201420142023Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf y Thomas Rothvoss201520172024Ryan Williams20112025David Zuckerman y Eshan Chattopadhyay2016
Artículos ganadores
Referencias
Categoría:Premios de ciencia e ingeniería