stringtranslate.com

Premio Godel

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 en Algoritmos y Teoría Computacional de la Asociación de Maquinaria de Computación ( 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 cuestión " P versus NP ", en una carta de 1956 a John von Neumann en la que Gödel preguntaba si un determinado problema NP-completo podría resolverse en tiempo cuadrático o lineal . [1]

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

  1. ^ 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
  2. ^ 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 
  3. ^ 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, ISBN 978-0-89232-896-3, archivado desde el original (PDF) el 22 de febrero de 2012
  4. ^ 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 
  5. ^ 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
  6. ^ 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
  7. ^ 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 
  8. ^ Halpern, José ; 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
  9. ^ Toda, Seinosuke (1991), "PP es tan difícil como la jerarquía de tiempo polinómico" (PDF) , SIAM Journal on Computing , 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , doi :10.1137/0220053 , ISSN  1095-7111 
  10. ^ 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
  11. ^ 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
  12. ^ 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
  13. ^ 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.
  14. ^ 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 
  15. ^ 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
  16. ^ 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
  17. ^ 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
  18. ^ 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
  19. ^ Alón, Noga ; Matías, 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 sobre Teoría de la Computación (STOC) en 1996.
  20. ^ 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
  21. ^ 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
  22. ^ 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
  23. ^ 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 
  24. ^ 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 ]
  25. ^ 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 
  26. ^ Mitchell, Joseph SB (1999), "Subdivisiones de guillotina subdivisiones poligonales aproximadas: un esquema simple de aproximación en tiempo polinomial para TSP geométrico, k-MST y problemas relacionados", SIAM Journal on Computing , 28 (4): 1298-1309, doi :10.1137/S0097539796309764, ISSN  1095-7111
  27. ^ 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 
  28. ^ 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.
  29. ^ 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. 
  30. ^ 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. 
  31. ^ 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. 
  32. ^ 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.
  33. ^ 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.
  34. ^ 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.
  35. ^ 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.
  36. ^ 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.
  37. ^ 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.
  38. ^ 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 .
  39. ^ 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 . ISBN 978-3-540-32731-8.
  40. ^ 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. 
  41. ^ 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.
  42. ^ "Una prueba constructiva del lema local general de Lovász". Revista de la ACM . 57 (2). 2010. doi : 10.1145/1667053. ISSN  0004-5411.
  43. ^ 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.
  44. ^ 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 . Sociedad de Matemáticas Industriales y Aplicadas (SIAM). 42 (3): 1245-1274. arXiv : 1003.3879 . doi :10.1137/100811258. ISSN  0097-5397. S2CID  1247279.
  45. ^ Cai, Jin-Yi; Chen, Xi (22 de junio de 2017). "Complejidad del recuento de 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.
  46. ^ 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.
  47. ^ 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. ISBN 9781450311151. S2CID  2602543.
  48. ^ 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.
  49. ^ 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.

Ver también

Notas

  1. ^ "La carta de Gödel". 2009-02-12.
  2. ^ ab "Premio Gödel 2017". Asociación Europea de Informática Teórica . EATCS . Consultado el 29 de marzo de 2017 .
  3. ^ "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 .
  4. ^ 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.
  5. ^ Los destinatarios lograron resultados innovadores al agregar datos de múltiples fuentes, Association for Computing Machinery , 30 de abril de 2014.
  6. ↑ Anuncio del Premio Gödel 2015 Archivado el 9 de diciembre de 2017 en Wayback Machine por Association for Computing Machinery .
  7. ^ "Mención del Premio Gödel 2018".
  8. ^ "Mención del Premio Gödel 2019".
  9. ^ "Mención del Premio Gödel 2020".
  10. ^ "Mención del Premio Gödel 2021".
  11. ^ "Mención del Premio Gödel 2022".
  12. ^ "Mención del Premio Gödel 2023".

Referencias