stringtranslate.com

Premio Gödel

Kurt Gödel
Kurt Gödel

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 Informática Teórica (EATCS) y el Grupo de Interés Especial sobre Algoritmos y Teoría Computacional de la Asociación de Maquinaria Computacional ( ACM SIGACT ). El premio recibe su nombre en honor a 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 preguntó si un 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 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 al premio, un artículo debe ser publicado en una revista arbitrada dentro de los últimos 14 (anteriormente 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é, que cumplen 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 artículos 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 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 , Advances in Computing Research, 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, 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
  9. ^ 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 2016-03-03 , consultado el 2010-06-08 
  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 de agosto de 2011
  12. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Pruebas interactivas y la dificultad de aproximar camarillas" (PDF) , Journal of the ACM , 43 (2): 268–292, doi : 10.1145/226643.226652 , ISSN  0004-5411
  13. ^ Arora, Sanjeev; Safra, Shmuel (1998), "Verificació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
  14. ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Verificación de pruebas y la dificultad 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 
  15. ^ Sénizergues, Géraud (2001), "L(A) = L(B)? resultados de decidibilidad de sistemas formales completos", Theor. Comput. Sci. , 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, 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 sobre el premio Gödel
  18. ^ Saks, Michael ; Zaharoglou, Fotios (2000), "El acuerdo de 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. ^ 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.1545Presentado 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", Anales de Matemáticas , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , ISSN  0003-486X
  21. ^ Razborov, Alexander A.; Rudich, Steven (1997), "Pruebas naturales", Revista de Ciencias de la Computación y de Sistemas , 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 tardar un tiempo polinomial", 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 gráfico en zigzag 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, MR  1888797, S2CID  120739405 
  24. ^ Reingold, Omer (2008), "Conectividad no dirigida en el espacio logarítmico", 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 temporal polinómica para problemas geométricos y del viajante euclidiano", 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), "Las subdivisiones de guillotina aproximan subdivisiones poligonales: 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 de inaproximabilidad óptima" (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. ^ Roughgarden, Tim; Tardos, Éva (2002). "¿Qué tan malo 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. ^ 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. 
  31. ^ Boneh, Dan; Franklin, Matthew (2003). "Cifrado basado en identidad a partir del emparejamiento de Weil". Revista SIAM de Informática . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . doi :10.1137/S0097539701398521. MR  2001745. 
  32. ^ Joux, Antoine (2004). "Un protocolo de una ronda para el método Diffie-Hellman tripartito". Revista de criptología . 17 (4): 263–276. doi : 10.1007/s00145-004-0312-y . MR  2090557. S2CID  3350730.
  33. ^ Fagin, Ronald; Lotem, Amnon; 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). "Esparcimiento espectral de grafos". 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 agrupamiento local para gráficos masivos y su aplicación a la partición de gráficos en 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 preacondicionamiento y resolución de sistemas lineales simétricos con predominancia diagonal". Revista SIAM sobre análisis de matrices y aplicaciones . 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) . Theoretical Computer Science . 375 (1–3): 227–270. doi :10.1016/j.tcs.2006.12.034.
  38. ^ O'Hearn, Peter (2007). "Recursos, concurrencia y razonamiento local" (PDF) . Ciencias de la computación teórica . 375 (1–3): 271–307. doi : 10.1016/j.tcs.2006.12.035 .
  39. ^ 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 clase en 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 redes, 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 . 60 (5). Association for Computing Machinery: 1–41. doi :10.1145/2528400. ISSN  0004-5411. S2CID  8964233.
  44. ^ Dyer, Martin; Richerby, David (2013). "Una dicotomía efectiva para el problema de satisfacción de restricciones de conteo". Revista SIAM de informática . 42 (3). Sociedad de Matemática Industrial y Aplicada (SIAM): 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 conteo de CSP con pesos complejos". Revista de la ACM . 64 (3). Association for Computing Machinery: 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 completamente homomórfico (nivelado) sin arranque". Actas de la 3.ª Conferencia sobre innovaciones en informática teórica . Nueva York, Nueva York, EE. UU.: ACM Press. pp. 309–325. doi :10.1145/2090236.2090262. ISBN . 9781450311151.S2CID2602543  .​
  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 complejidad de extensión exponencial". Revista de la ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi :10.1145/3127497. S2CID  47045361.
  50. ^ Williams, Ryan (junio de 2011). "Límites inferiores de circuitos ACC no uniformes". 26.ª Conferencia anual sobre complejidad computacional del IEEE de 2011. IEEE. págs. 115-125. doi :10.1109/ccc.2011.36. ISBN 978-1-4577-0179-5.

Véase también

Notas

  1. ^ "La carta de Gödel". 12 de febrero de 2009.
  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 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 .
  4. ^ 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 el 1 de junio de 2013 en Wayback Machine , Association for Computing Machinery , 29 de mayo de 2013.
  5. ^ Los destinatarios obtuvieron 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".
  13. ^ "Mención del Premio Gödel 2024".

Referencias