El Premio Gödel es el Premio Kurt Gödel en Teoría de Sistemas Computacionales , presentado anualmente por ACM SIGACT , ( Grupo de Interés Especial en Algoritmos y Teoría de la Computación ) y EATCS , ( Asociación Europea de Ciencias Informáticas Teóricas ) por trabajos sobresalientes en lógica e informática teórica .
El premio se otorga desde 1993 y va acompañado de un premio en efectivo de $ 5,000 [1] . El premio tiene lugar ya sea en el simposio americano STOC , ( Simposio sobre Teoría de la Computación ), o en la conferencia europea ICALP , ( Coloquio Internacional sobre Autómatas, Lenguajes y Programación ). El requisito principal para el trabajo es la fecha de la primera publicación: solo se pueden nominar trabajos que no tengan más de 14 años.
Año | Nombre | notas |
---|---|---|
1993 | Laszlo Babai , Shafi Goldwasser , Silvio Micali , Shlomo Moran y Charles Rakoff | para desarrollar sistemas de prueba interactivos [2] [3] . |
1994 | Johan Hostad | para probar un límite inferior exponencial en el conteo de paridad utilizando esquemas booleanos de profundidad constante [4] [5] . |
1995 | Neil Immerman , Robert Shelepcheni | para el teorema de Immermann-Shelepcheni ( teoría de la complejidad computacional ) [6] [7] . |
1996 | Mark Jerram , Alistair Sinclair | por su investigación sobre las cadenas de Markov y la aproximación de la permanente de matrices [8] [9] . |
1997 | Joseph Halpern , Yoram Moisés | para la definición formal del concepto de "conocimiento" en entornos distribuidos [10] [11] . |
1998 | Seinosuke Toda | para el teorema de Toda , que mostró la relación entre las clases de complejidad PP y PH [12] [13] . |
1999 | pedro orilla | para el algoritmo de Shor para factorizar números en una cantidad polinomial de tiempo en una computadora cuántica [14] [15] . |
2000 | Moshe Vardy , Pierre Wolper | por su investigación sobre verificación de modelos con autómatas finitos [16] [17] . |
2001 | Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani Shmuel Safra , Sudan , Mario Szegedi | para el teorema PCP y su aplicación [18] [19] . |
2002 | Jéro Senizerg | para probar la solucionabilidad de la equivalencia de autómatas pushdown deterministas [20] [21] . |
2003 | Yoav Freund y Robert Shapire | para el algoritmo AdaBoost [22] [23] . |
2004 | Maurice Herlihy , Michael Sachs Nir Shavit y Fotios Zaharoglu | para la aplicación de la topología a la teoría de la computación distribuida [24] [25] . |
2005 | Noga Alon , Yossi Matias , Mario Szegedi | para la investigación fundamental en el campo de los algoritmos de transmisión [26] [27] . |
2006 | Manindra Agrawal , Niraj Kayal , Nitin Saxena | para la prueba de Agrawal-Kayala-Sajonia [28] [29] . |
2007 | Alexander Razborov , Steven Rudich | para " pruebas naturales " [30] [31] . |
2008 | Teng ShanhuaDaniel Speelman | para el " análisis suave " de algoritmos [32] . |
2009 | Omer Reingold , Salil Wadhan , Avi Wigderson | para el producto en zigzag de grafos y encontrar un algoritmo determinista , logarítmico en memoria , para resolver el problema de conectividad st no dirigida[33] . |
2010 | Sanjiv AroraJoseph Mitchell | para el descubrimiento del esquema de aproximación polinomial temporal (PTAS) para el problema del viajante de comercio euclidiano [34] . |
2011 | Johan Hostad | para probar la no aproximabilidad de varios problemas combinatorios [35] . |
2012 | Elias Koutsoupias , Christos Papadimitriou , Tim Roukhgarden , Eva Tardos , Noam Nisan , Amir Ronen | por su contribución a la comprensión de cómo el comportamiento egoísta de los usuarios y proveedores de servicios afecta el comportamiento de Internet y otros sistemas informáticos complejos [36] . |
2013 | Antoine Joux , Dan Bonet , Matthew C. Franklin | por su trabajo sobre criptografía [37] [38] . |
2014 | Ronald Fagin , Amnon Lotem , Moni Naor | para algoritmos de agregación óptimos para Middleware [39] . |
2015 | Daniel Spielman , Teng Shanhua | para una serie de artículos sobre la solución rápida de sistemas de ecuaciones lineales [40] [41] . |
2016 | Stephen Brooks , Peter O'Hearn | para el desarrollo de una lógica de partición paralela [42] . |
2017 | Cynthia Dwork , Frank McSherry , Kobe Nissim , Adam D. Smith | Privacidad diferencial [43] . |
2018 | Oded Regev | Aprendizaje con errores [44] . |
2019 | Irit Dinur [45] | para una prueba nueva y más simple del teorema PCP por el método de amplificación de rendija [ 46] . |
2020 | Robin Moser y Gabor Tardos | para la versión algorítmica del lema local de Lovas [47] |
2021 | Andrey Bulatov , Jin-Yi Cai, Xi Chen, Martin Dyer, David Richerby | por su trabajo sobre la clasificación de la complejidad de conteo de los problemas de satisfacción de restricciones |
del premio Gödel | Ganadores|
---|---|
1990 |
|
2000 | |
2010 |
|