El Premio Gödel se otorga desde 1993. El premio se otorga alternativamente en ICALP (años pares) y STOC (años impares). STOC es el Simposio ACM sobre Teoría de la Computación , una de las principales conferencias norteamericanas en informática teórica, mientras que ICALP es el Coloquio Internacional sobre Autómatas, Lenguajes y Programación , una de las principales conferencias europeas en el campo. Para ser elegible para el premio, un artículo debe haber sido publicado en una revista arbitrada dentro de los últimos 14 (antes 7) años. El premio incluye una recompensa de 5000 dólares estadounidenses. [2]
El ganador del premio es seleccionado por un comité de seis miembros. El presidente de la EATCS y el presidente del SIGACT designan cada uno a tres miembros del comité, para desempeñar mandatos escalonados de tres años. El comité está presidido alternativamente por representantes de EATCS y SIGACT.
A diferencia del Premio Gödel, que reconoce trabajos destacados, el Premio Knuth se otorga a personas por su impacto general en el campo.
Destinatarios
Trabajos 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 pequeña profundidad" (PDF) , en Micali, Silvio (ed.), Aleatoriedad y computación , Avances en la investigación en computación, vol. 5, JAI Press, págs. 6-20, ISBN978-0-89232-896-3, archivado desde el original (PDF) el 22 de febrero de 2012
^ 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", Información y Computación , 82 (1): 93–133, doi : 10.1016/0890-5401(89)90067-9 , ISSN 0890 -5401
^ Jerrum, M.; Sinclair, Alistair (1989), "Aproximación a lo permanente", SIAM Journal on Computing , 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 , doi :10.1137/0218077, ISSN 1095-7111
^ 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, archivado desde el original (PDF) el 3 de marzo de 2016 , consultado el 8 de junio de 2010
^ Shor, Peter W. (1997), "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica", SIAM Journal on Computing , 26 (5): 1484–1509, arXiv : quant-ph/9508027 , doi :10.1137/S0097539795293172, ISSN 1095-7111, S2CID 2337707
^ Vardi, Moshe Y.; Wolper, Pierre (1994), "Razonamiento sobre cálculos infinitos" (PDF) , Información y Computación , 115 (1): 1–37, doi :10.1006/inco.1994.1092, ISSN 0890-5401, archivado desde el original (PDF) el 25/08/2011
^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Pruebas interactivas y la dureza de las camarillas aproximadas" (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 10 de junio de 2011.
^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudán, Madhu; Szegedy, Mario (1998), "Verificación de pruebas y 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 10 de junio de 2011
^ Sénizergues, Géraud (2001), "¿L (A) = L (B)? La decidibilidad resulta de sistemas formales completos", Theor. Computadora. Ciencia. , 251 (1): 1–166, doi :10.1016/S0304-3975(00)00285-1, ISSN 0304-3975
^ Freund, Y.; Schapire, RE (1997), "Una generalización teórica de decisiones 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, Mauricio ; 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
^ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES está en P", Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , ISSN 0003-486X
^ Razborov, Alejandro 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 suele tomar tiempo polinómico", J. ACM , 51 (3): 385–463, arXiv : math/0212413 , doi :10.1145/990308.990310, ISSN 0004-5411
^ 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", Annals of Mathematics , 155 (1): 157–187, CiteSeerX 10.1.1.236.8669 , doi :10.2307/ 3062153, ISSN 0003-486X, JSTOR 3062153, SEÑOR 1888797, S2CID 120739405
^ 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 polinómico para viajantes de comercio 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), "Subdivisiones de guillotina subdivisiones poligonales aproximadas: un esquema simple de aproximación en tiempo polinómico para TSP geométrico, k-MST y problemas relacionados", SIAM Journal on Computing , 28 (4): 1298-1309, doi :10.1137/S0097539796309764, ISSN 1095-7111
^ Håstad, Johan (2001), "Algunos resultados óptimos de inaccesibilidad" (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, Elías; Papadimitriou, Christos (2009). "Equilibrios en el peor de los casos". Revisión de informática . 3 (2): 65–69. doi :10.1016/j.cosrev.2009.04.003.
^ Jardín áspero, 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.
^ Nisán, 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/juego.1999.0790.
^ Boneh, Dan; Franklin, Mateo (2003). "Cifrado basado en identidad del emparejamiento 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, Amnón; Naor, Moni (2003). "Algoritmos de agregación óptimos para middleware". Revista de Ciencias de la Computación y de 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 agrupación local para gráficos masivos y su aplicación a la partición 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 el preacondicionamiento y la resolución de sistemas lineales simétricos y diagonalmente dominantes". Revista SIAM sobre Análisis y Aplicaciones de Matrices . 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 .
^ Dtrabajo, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adán (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 sobre informática. vol. 3876. Springer-Verlag. págs. 265–284. doi : 10.1007/11681878_14 . ISBN978-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 espacios". 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 . 60 (5). Asociación de Maquinaria de Computación: 1–41. doi :10.1145/2528400. ISSN 0004-5411. S2CID 8964233.
^ Dyer, Martín; Richerby, David (2013). "Una dicotomía eficaz para el problema de la satisfacción de las restricciones de conteo". Revista SIAM de Computación . 42 (3). Sociedad de Matemáticas Industriales y Aplicadas (SIAM): 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 del recuento de CSP con pesos complejos". Revista de la ACM . 64 (3). Asociación de Maquinaria de Computación: 1–39. arXiv : 1111.2384 . doi :10.1145/2822891. ISSN 0004-5411. S2CID 1053684.
^ Brakerski, Zvika; Vaikuntanathan, Vinod (enero de 2014). "Cifrado eficiente totalmente homomórfico de (estándar) $\mathsf{LWE}$". Revista SIAM de Computación . 43 (2): 831–871. doi :10.1137/120868669. hdl : 1721.1/115488 . ISSN 0097-5397. S2CID 8831240.
^ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "Cifrado (nivelado) totalmente homomórfico sin arranque". Actas de la 3ª Conferencia sobre Innovaciones en Informática Teórica . Nueva York, Nueva York, Estados Unidos: ACM Press. págs. 309–325. doi :10.1145/2090236.2090262. ISBN9781450311151. S2CID 2602543.
^ Fiorini, Samuel; Massar, Serge; Pokutta, Sebastián; Tiwary, Hans Raj; de Wolf, Ronald (2015). "Límites inferiores exponenciales para politopos en optimización combinatoria". Revista de la ACM . 62 (2): 17:1–17:23. arXiv : 1111.0837 . doi :10.1145/2716307. S2CID 7372000.
^ Rothvoss, Thomas (2017). "El politopo coincidente tiene una complejidad de extensión exponencial". Revista de la ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi :10.1145/3127497. S2CID 47045361.
^ Williams, Ryan (junio de 2011). "Límites inferiores del circuito ACC no uniformes". 26ª Conferencia Anual del IEEE 2011 sobre Complejidad Computacional . IEEE: 115–125. doi :10.1109/ccc.2011.36. ISBN978-1-4577-0179-5.
^ ab "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 algorítmica de juegos". 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 informáticos citados por innovaciones que mejoran la seguridad Archivado el 1 de junio de 2013 en Wayback Machine , Association for Computing Machinery , 29 de mayo de 2013.
^ Los destinatarios lograron resultados innovadores al agregar datos de múltiples fuentes, Association for Computing Machinery , 30 de abril de 2014.