El Premio Gödel es un premio anual para trabajos destacados en el área de la informática teórica , otorgado conjuntamente por la Asociación Europea de Ciencias de la Computación Teórica (EATCS) y el Grupo de Interés Especial de la Asociación de Maquinaria de Computación sobre Algoritmos y Teoría Computacional ( ACM SIGACT ). El premio lleva el nombre de Kurt Gödel . La conexión de Gödel con la informática teórica es que fue el primero en mencionar la pregunta " P versus NP ", en una carta de 1956 a John von Neumann en la que Gödel preguntaba si cierto problema NP-completo podía resolverse en tiempo cuadrático o lineal.[1]
El Premio Gödel se otorga desde 1993. El premio se otorga en STOC ( Simposio ACM sobre Teoría de la Computación , uno de los principales congresos norteamericanos en informática teórica) o ICALP ( Coloquio Internacional sobre Autómatas, Lenguajes y Programación , uno de los las principales conferencias europeas en la materia). Para ser elegible para el premio, un artículo debe ser publicado en una revista arbitrada dentro de los últimos 14 (antes, 7) años. El premio incluye una recompensa de US $ 5000. [2]
El ganador del premio es seleccionado por un comité de seis miembros. El presidente de EATCS y el presidente de SIGACT designan cada uno a tres miembros del comité, para servir términos escalonados de tres años. El comité está presidido alternativamente por representantes de EATCS y SIGACT.
Destinatarios
Año | Nombre (s) | Notas | Año de publicación | |
---|---|---|---|---|
1993 | László Babai , Shafi Goldwasser , Silvio Micali , Shlomo Moran y Charles Rackoff | para el desarrollo de sistemas de prueba interactivos | 1988, [documento 1] 1989 [documento 2] | |
1994 | Johan Håstad | para un límite inferior exponencial en el tamaño de los circuitos booleanos de profundidad constante (para la función de paridad ). | 1989 [documento 3] | |
1995 | Neil Immerman y Róbert Szelepcsényi | para el teorema de Immerman-Szelepcsényi sobre la complejidad espacial no determinista | 1988, [documento 4] 1988 [documento 5] | |
1996 | Mark Jerrum y Alistair Sinclair | para trabajar en cadenas de Markov y la aproximación de la permanente de una matriz | 1989, [documento 6] 1989 [documento 7] | |
1997 | Joseph Halpern y Yoram Moses | para definir una noción formal de "conocimiento" en entornos distribuidos | 1990 [documento 8] | |
1998 | Seinosuke Toda | para el teorema de Toda que mostró una conexión entre las soluciones de conteo ( PP ) y la alternancia de cuantificadores ( PH ) | 1991 [documento 9] | |
1999 | Peter Shor | para el algoritmo de Shor para factorizar números en tiempo polinomial en una computadora cuántica | 1997 [documento 10] | |
2000 | Moshe Y. Vardi y Pierre Wolper | para trabajar en lógica temporal con autómatas finitos | 1994 [documento 11] | |
2001 | Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Carsten Lund , László Lovász , Rajeev Motwani , Shmuel Safra , Madhu Sudan y Mario Szegedy | para el teorema de PCP y sus aplicaciones a la dureza de aproximación | 1996, [documento 12] 1998, [documento 13] 1998 [documento 14] | |
2002 | Géraud Sénizergues | para demostrar que la equivalencia de los autómatas de empuje deterministas es decidible | 2001 [documento 15] | |
2003 | Yoav Freund y Robert Schapire | para el algoritmo AdaBoost en aprendizaje automático | 1997 [documento 16] | |
2004 | Maurice Herlihy , Michael Saks , Nir Shavit y Fotios Zaharoglou | para aplicaciones de topología a la teoría de la computación distribuida | 1999, [documento 17] 2000 [documento 18] | |
2005 | Noga Alon , Yossi Matias y Mario Szegedy | por su contribución fundamental a los algoritmos de transmisión | 1999 [documento 19] | |
2006 | Manindra Agrawal , Neeraj Kayal , Nitin Saxena | para la prueba de primalidad de AKS | 2004 [documento 20] | |
2007 | Alexander Razborov , Steven Rudich | para pruebas naturales | 1997 [documento 21] | |
2008 | Daniel Spielman , Shanghua Teng | para análisis suavizado de algoritmos | 2004 [documento 22] | |
2009 | Omer Reingold , Salil Vadhan y Avi Wigderson | para el producto en zig-zag de gráficos y conectividad no dirigida en el espacio de registro | 2002, [documento 23] 2008 [documento 24] | |
2010 | Sanjeev Arora , Joseph SB Mitchell | por su descubrimiento simultáneo de un esquema de aproximación de tiempo polinomial (PTAS) para el Problema del vendedor ambulante euclidiano (ETSP) | 1998, [documento 25] 1999 [documento 26] | |
2011 | Johan Håstad | para demostrar resultados óptimos de inapropiabilidad para varios problemas combinatorios | 2001 [documento 27] | |
2012 | Elias Koutsoupias , Christos Papadimitriou , Noam Nisan , Amir Ronen | , Tim Roughgarden y Éva Tardospara sentar las bases de la teoría algorítmica de juegos [3] | 2009, [documento 28] 2002, [documento 29] 2001 [documento 30] | |
2013 | Dan Boneh , Matthew K. Franklin y Antoine Joux | para el intercambio de claves Diffie-Hellman entre varias partes y el esquema Boneh-Franklin en criptografía [4] | 2003, [documento 31] 2004 [documento 32] | |
2014 | Ronald Fagin , Amnon Lotem | y Moni Naorpara algoritmos de agregación óptimos para middleware [5] | 2003, [documento 33] | |
2015 | Daniel Spielman , Shanghua Teng | por su serie de artículos sobre solucionadores laplacianos en tiempo casi lineal [6] | 2011 [documento 34] 2013 [documento 35] 2014 [documento 36] | |
2016 | Stephen Brookes y Peter W. O'Hearn | por su invención de la lógica de separación concurrente | 2007, [documento 37] 2007 [documento 38] | |
2017 [2] | Cynthia Dwork , Frank McSherry , Kobbi Nissim y Adam D. Smith | por la invención de la privacidad diferencial | 2006 [documento 39] | |
2018 [7] | Oded Regev | para introducir el aprendizaje de errores problema | 2009 [documento 40] | |
2019 [8] | Irit Dinur | por su nueva prueba del teorema PCP por amplificación de brecha | 2007 [documento 41] | |
2020 [9] | Robin Moser y Gábor Tardos | por su prueba constructiva del lema local de Lovász | 2010 [documento 42] | |
2021 [10] | Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer y David Richerby | por su trabajo en la clasificación de la complejidad de conteo de los problemas de satisfacción de restricciones | 2013 [documento 43] 2013 [documento 44] 2017 [documento 45] |
Papeles ganadores
- ^ Babai, László; Moran, Shlomo (1988), "Juegos de Arthur-Merlin: un sistema de prueba aleatorio y una jerarquía de clases de complejidad" (PDF) , Journal of Computer and System Sciences , 36 (2): 254-276, doi : 10.1016 / 0022 -0000 (88) 90028-1 , ISSN 0022-0000
- ^ Goldwasser, S .; Micali, S .; Rackoff, C. (1989), "La complejidad del conocimiento de los sistemas de prueba interactivos" (PDF) , SIAM Journal on Computing , 18 (1): 186–208, CiteSeerX 10.1.1.397.4002 , doi : 10.1137 / 0218012 , ISSN 1095 -7111
- ^ Håstad, Johan (1989), "Límites inferiores casi óptimos para circuitos de profundidad pequeña" (PDF) , en Micali, Silvio (ed.), Randomness and Computation , Advances in Computing Research, 5 , JAI Press, págs. 6-20, ISBN 978-0-89232-896-3, archivado desde el original (PDF) el 2012-02-22
- ^ Immerman, Neil (1988), "El espacio no determinista está cerrado bajo complementación" (PDF) , SIAM Journal on Computing , 17 (5): 935–938, CiteSeerX 10.1.1.54.5941 , doi : 10.1137 / 0217058 , ISSN 1095-7111
- ^ Szelepcsényi, R. (1988), "El método de enumeración forzada para autómatas no deterministas" (PDF) , Acta Informatica , 26 (3): 279–284, doi : 10.1007 / BF00299636 , hdl : 10338.dmlcz / 120489 , S2CID 10838178
- ^ Sinclair, A .; Jerrum, M. (1989), "Recuento aproximado, generación uniforme y mezcla rápida de cadenas de Markov", Information and Computation , 82 (1): 93-133, doi : 10.1016 / 0890-5401 (89) 90067-9 , ISSN 0890 -5401
- ^ Jerrum, M .; Sinclair, Alistair (1989), "Aproximando lo permanente", SIAM Journal on Computing , 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 , doi : 10.1137 / 0218077 , ISSN 1095-7111
- ^ Halpern, Joseph ; Moses, Yoram (1990), "Conocimiento y conocimiento común en un entorno distribuido" (PDF) , Journal of the ACM , 37 (3): 549–587, arXiv : cs / 0006009 , doi : 10.1145 / 79147.79161 , S2CID 52151232
- ^ Toda, Seinosuke (1991), "PP es tan difícil como la jerarquía de tiempo polinomial" (PDF) , SIAM Journal on Computing , 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , doi : 10.1137 / 0220053 , ISSN 1095-7111
- ^ Shor, Peter W. (1997), "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica" (PDF) , SIAM Journal on Computing , 26 (5): 1484-1509, arXiv : quant-ph / 9508027 , doi : 10.1137 / S0097539795293172 , ISSN 1095-7111 , S2CID 2337707[ enlace muerto permanente ]
- ^ Vardi, Moshe Y .; Wolper, Pierre (1994), "Reasoning about infinite computations" (PDF) , Information and Computation , 115 (1): 1–37, doi : 10.1006 / inco.1994.1092 , ISSN 0890-5401 , archivado desde el original (PDF) el 2011-08-25
- ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Pruebas interactivas y la dureza de las camarillas que se aproximan" (PDF) , Journal of the ACM , 43 (2): 268-292, doi : 10.1145 / 226643.226652 , ISSN 0004-5411
- ^ Arora, Sanjeev; Safra, Shmuel (1998), "Comprobación probabilística de pruebas: una nueva caracterización de NP" (PDF) , Journal of the ACM , 45 (1): 70-122, doi : 10.1145 / 273865.273901 , ISSN 0004-5411 , S2CID 751563 , archivado desde el original (PDF) el 2011-06-10
- ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudán, Madhu; Szegedy, Mario (1998), "Verificación de la prueba y la dureza de los problemas de aproximación" (PDF) , Journal of the ACM , 45 (3): 501–555, CiteSeerX 10.1.1.145.4652 , doi : 10.1145 / 278298.278306 , ISSN 0004 -5411 , S2CID 8561542 , archivado desde el original (PDF) el 2011-06-10
- ^ Sénizergues, Géraud (2001), "L (A) = L (B)? La decidibilidad resulta de sistemas formales completos", Theor. Computación. Sci. , 251 (1): 1–166, doi : 10.1016 / S0304-3975 (00) 00285-1 , ISSN 0304-3975
- ^ Freund, Y .; Schapire, RE (1997), "Una generalización de la teoría de la decisión del aprendizaje en línea y una aplicación para impulsar" (PDF) , Journal of Computer and System Sciences , 55 (1): 119-139, doi : 10.1006 / jcss. 1997.1504 , ISSN 1090-2724
- ^ Herlihy, Maurice ; Shavit, Nir (1999), "La estructura topológica de la computabilidad asincrónica" (PDF) , Journal of the ACM , 46 (6): 858–923, CiteSeerX 10.1.1.78.1455 , doi : 10.1145 / 331524.331529 , S2CID 5797174. Conferencia del premio Gödel
- ^ Saks, Michael ; Zaharoglou, Fotios (2000), "El acuerdo k -set sin espera es imposible: la topología del conocimiento público", SIAM Journal on Computing , 29 (5): 1449–1483, doi : 10.1137 / S0097539796307698
- ^ Alon, Noga ; Matias, Yossi; Szegedy, Mario (1999), "La complejidad espacial de la aproximación de los momentos de frecuencia" (PDF) , Journal of Computer and System Sciences , 58 (1): 137-147, doi : 10.1006 / jcss.1997.1545. Presentado por primera vez en el Simposio de Teoría de la Computación (STOC) en 1996.
- ^ Agrawal, M .; Kayal, N .; Saxena, N. (2004), "PRIMES is in P", Annals of Mathematics , 160 (2): 781–793, doi : 10.4007 / annals.2004.160.781 , ISSN 0003-486X
- ^ Razborov, Alexander A .; Rudich, Steven (1997), "Pruebas naturales", Journal of Computer and System Sciences , 55 (1): 24–35, doi : 10.1006 / jcss.1997.1494 , ISSN 0022-0000 , ECCC TR94-010
- ^ Spielman, Daniel A .; Teng, Shang-Hua (2004), "Análisis suavizado de algoritmos: por qué el algoritmo simplex generalmente toma tiempo polinomial" (PDF) , J. ACM , 51 (3): 385–463, arXiv : math / 0212413 , doi : 10.1145 /990308.990310 , ISSN 0004-5411[ enlace muerto permanente ]
- ^ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Ondas de entropía, el producto del gráfico en zig-zag y nuevos expansores de grado constante" (PDF) , Annals of Mathematics , 155 (1): 157-187, CiteSeerX 10.1.1.236.8669 , doi : 10.2307 / 3062153 , ISSN 0003-486X , JSTOR 3062153 , MR 1888797 , S2CID 120739405[ enlace muerto permanente ]
- ^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio de registro" , J. ACM , 55 (4): 1–24, doi : 10.1145 / 1391289.1391291 , ISSN 0004-5411 , S2CID 207168478[ enlace muerto permanente ]
- ^ Arora, Sanjeev (1998), "Esquemas de aproximación de tiempo polinomial para el viajante de ventas euclidiano y otros problemas geométricos", Journal of the ACM , 45 (5): 753–782, CiteSeerX 10.1.1.23.6765 , doi : 10.1145 / 290179.290180 , ISSN 0004-5411 , S2CID 3023351
- ^ Mitchell, Joseph SB (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polinomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", SIAM Journal on Computing , 28 (4): 1298-1309, doi : 10.1137 / S0097539796309764 , ISSN 1095-7111
- ^ Håstad, Johan (2001), "Algunos resultados óptimos de inaproximabilidad" (PDF) , Journal of the ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145 / 502090.502098 , ISSN 0004-5411 , S2CID 5120748
- ^ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Equilibrios en el peor de los casos". Revisión de Ciencias de la Computación . 3 (2): 65–69. doi : 10.1016 / j.cosrev.2009.04.003 .
- ^ Roughgarden, Tim; Tardos, Éva (2002). "¿Qué tan grave es el enrutamiento egoísta?". Revista de la ACM . 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . doi : 10.1145 / 506147.506153 . S2CID 207638789 .
- ^ Nisan, Noam; Ronen, Amir (2001). "Diseño de mecanismos algorítmicos". Juegos y comportamiento económico . 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . doi : 10.1006 / game.1999.0790 .
- ^ Boneh, Dan; Franklin, Matthew (2003). "Cifrado basado en identidad del emparejamiento de Weil". Revista SIAM de Computación . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . doi : 10.1137 / S0097539701398521 . Señor 2001745 .
- ^ Joux, Antoine (2004). "Un protocolo de una ronda para Diffie-Hellman tripartito". Revista de criptología . 17 (4): 263-276. doi : 10.1007 / s00145-004-0312-y . Señor 2090557 . S2CID 3350730 .
- ^ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Algoritmos de agregación óptimos para middleware". Revista de Ciencias de la Computación y Sistemas . 66 (4): 614–656. arXiv : cs / 0204046 . doi : 10.1016 / S0022-0000 (03) 00026-6 .
- ^ Spielman, Daniel A .; Teng, Shang-Hua (2011). "Esparsificación espectral de gráficos". Revista SIAM de Computación . 40 (4): 981–1025. arXiv : 0808.4134 . doi : 10.1137 / 08074489X . ISSN 0097-5397 . S2CID 9646279 .
- ^ Spielman, Daniel A .; Teng, Shang-Hua (2013). "Un algoritmo de agrupamiento local para gráficos masivos y su aplicación al particionamiento de gráficos de tiempo casi lineal". Revista SIAM de Computación . 42 (1): 1–26. arXiv : 0809.3232 . doi : 10.1137 / 080744888 . ISSN 0097-5397 . S2CID 9151077 .
- ^ Spielman, Daniel A .; Teng, Shang-Hua (2014). "Algoritmos de tiempo casi lineal para preacondicionamiento y resolución de sistemas lineales simétricos, diagonalmente dominantes". Revista SIAM sobre Análisis y Aplicaciones Matriciales . 35 (3): 835–885. arXiv : cs / 0607105 . doi : 10.1137 / 090771430 . ISSN 0895-4798 . S2CID 1750944 .
- ^ Brookes, Stephen (2007). "Una semántica para la lógica de separación concurrente" (PDF) . Informática Teórica . 375 (1-3): 227-270. doi : 10.1016 / j.tcs.2006.12.034 .
- ^ O'Hearn, Peter (2007). "Recursos, concurrencia y razonamiento local" (PDF) . Informática Teórica . 375 (1-3): 271-307. doi : 10.1016 / j.tcs.2006.12.035 .
- ^ Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). Calibración del ruido a la sensibilidad en el análisis de datos privados . Teoría de la criptografía (TCC). Apuntes de conferencias en informática. 3876 . Springer-Verlag. págs. 265-284. doi : 10.1007 / 11681878_14 . ISBN 978-3-540-32731-8.
- ^ Regev, Oded (2009). "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía". Revista de la ACM . 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . doi : 10.1145 / 1568318.1568324 . S2CID 207156623 .
- ^ Dinur, Irit (2007). "El teorema de PCP por amplificación de brecha" . Revista de la ACM . 54 (3): 12 – es. doi : 10.1145 / 1236457.1236459 . S2CID 53244523 .
- ^ "Una prueba constructiva del Lema local general de Lovász". Revista de la ACM . 57 (2). 2010. doi : 10.1145 / 1667053 . ISSN 0004-5411 .
- ^ Bulatov, Andrei A. (2013). "La complejidad del problema de satisfacción de la restricción de conteo". Revista de la ACM . Asociación de Maquinaria de Computación (ACM). 60 (5): 1–41. doi : 10.1145 / 2528400 . ISSN 0004-5411 . S2CID 8964233 .
- ^ Dyer, Martin; Richerby, David (2013). "Una dicotomía eficaz para el problema de satisfacción de la restricción de conteo". Revista SIAM de Computación . Sociedad de Matemáticas Industriales y Aplicadas (SIAM). 42 (3): 1245-1274. arXiv : 1003.3879 . doi : 10.1137 / 100811258 . ISSN 0097-5397 . S2CID 1247279 .
- ^ Cai, Jin-Yi; Chen, Xi (22 de junio de 2017). "Complejidad de contar CSP con pesos complejos". Revista de la ACM . Asociación de Maquinaria de Computación (ACM). 64 (3): 1–39. arXiv : 1111.2384 . doi : 10.1145 / 2822891 . ISSN 0004-5411 . S2CID 1053684 .
Ver también
- Lista de premios de informática
Notas
- ^ "La carta de Gödel" . 2009-02-12.
- ^ a b "Premio Gödel 2017" . Asociación Europea de Informática Teórica . EATCS . Consultado el 29 de marzo de 2017 .
- ^ "Tres artículos citados para sentar las bases del crecimiento en la teoría de juegos algorítmicos" . 16 de mayo de 2012. Archivado desde el original el 18 de julio de 2013 . Consultado el 16 de mayo de 2012 .
- ^ ACM Group presenta el premio Gödel por avances en criptografía: tres científicos informáticos citados por innovaciones que mejoran la seguridad Archivado 2013-06-01 en Wayback Machine , Association for Computing Machinery , 29 de mayo de 2013.
- ^ Los destinatarios lograron resultados innovadores para la agregación de datos de múltiples fuentes , Asociación de maquinaria de computación , 30 de abril de 2014.
- ^ Anuncio del Premio Gödel 2015 Archivado el 9 de diciembre de 2017 en Wayback Machine por la Asociación de Maquinaria de Computación .
- ^ "Citación del Premio Gödel 2018" .
- ^ "Cita Premio Gödel 2019" .
- ^ "Citación del Premio Gödel 2020" .
- ^ "Cita Premio Gödel 2021" .
Referencias
- Sitio web del premio con lista de ganadores