Premio Gödel

Premio Gödel
Premio a informática, computación teórica
Otorgado por Asociación Europea para la Informática Teórica y ACM
Historia
Inspirado por Kurt Gödel
Primera entrega 1993

El Premio Gödel es un premio que se entrega a autores de artículos científicos destacados en teoría de la computación. Es otorgado por la European Association for Theoretical Computer Science (EATCS) y el Grupo de Interés Especial de Algoritmos y Teoría de la Computación de la Association for Computing Machinery (ACM SIGACT).[1]​ Su nombre se debe al matemático Kurt Gödel, quien en una carta de 1956 dirigida a John von Neumann planteó por primera vez el problema de P vs NP.[2]​

El premio se entrega anualmente desde 1993, intercaladamente tanto en el EATCS International Colloquium on Automata, Languages, and Programming (ICALP) como en el ACM Symposium on Theory of Computing (STOC), dos importantes congresos en el área. Los artículos nominados deben haber sido publicados hace máximo 14 años atrás (anteriormente eran sólo 7 años). Además de la distinción, incluye un aporte de 5000 dólares.[1]​

Ganadores

Los distintos ganadores del premio han sido los siguientes:[1]​

Versión Autores Razón Año
publicación
1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran y Charles Rackoff Por el desarrollo de sistemas de demostración interactivos. 1988[paper 1]​
1989[paper 2]​
1994 Johan Håstad Por encontrar una cota inferior exponencial en función del tamaño de profundidad constante de un circuito booleano para la función paridad. 1989[paper 3]​
1995 Neil Immerman y Róbert Szelepcsényi Por el Teorema de Immerman-Szelepcsényi, sobre complejidad espacial no-determinista. 1988[paper 4]​
1988[paper 5]​
1996 Mark Jerrum y Alistair Sinclair Por sus trabajos sobre cadenas de Márkov y la aproximación del permanente de una matriz. 1989[paper 6]​
1989[paper 7]​
1997 Joseph Halpern y Yoram Moses Por definir una noción formal de «conocimiento» en entornos distribuidos. 1990[paper 8]​
1998 Seinosuke Toda Por el Teorema de Toda, que demuestra una conexión entre contar soluciones (PP) y alternar cuantificadores (PH). 1991[paper 9]​
1999 Peter Shor Por el algoritmo de Shor para factorizar números en tiempo polinómico en un computador cuántico. 1997[paper 10]​
2000 Moshe Y. Vardi y Pierre Wolper Por su aporte en lógica temporal con autómatas finitos. 1994[paper 11]​
2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan y Mario Szegedy Por el teorema PCP y sus aplicaciones a la dificultad de la aproximación. 1996[paper 12]​
1998[paper 13]​
1998[paper 14]​
2002 Géraud Sénizergues Por demostrar que la equivalencia de autómatas de pila deterministas es decidible. 2001[paper 15]​
2003 Yoav Freund y Robert Schapire Por el algoritmo AdaBoost. 1997[paper 16]​
2004 Maurice Herlihy, Mike Saks, Nir Shavit y Fotios Zaharoglou Por aplicar topología a la teoría de computación distribuida. 1999[paper 17]​
2000[paper 18]​
2005 Noga Alon, Yossi Matias y Mario Szegedy Por su contribución fundacional a los algoritmos de streaming 1999[paper 19]​
2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena Por el test de primalidad AKS 2004[paper 20]​
2007 Alexander Razborov y Steven Rudich Por las demostraciones naturales 1997[paper 21]​
2008 Shanghua Teng y Daniel Spielman Por el análisis smoothed de algoritmos 2004[paper 22]​
2009 Omer Reingold, Avi Wigderson y Salil Vadhan 2002[paper 23]​
2008[paper 24]​
2010 Sanjeev Arora y Joseph S. B. Mitchell 1998[paper 25]​
1999[paper 26]​
2011 Johan Håstad 2001[paper 27]​
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden y Éva Tardos 2009[paper 28]​
2002[paper 29]​
2001[paper 30]​
2013 Dan Boneh, Matthew K. Franklin y Antoine Joux 2003[paper 31]​
2004[paper 32]​
2014 Ronald Fagin, Amnon Lotem y Moni Naor 2003[paper 33]​
2015 Daniel A. Spielman y Shang-Hua Teng 2011[paper 34]​
2013[paper 35]​
2014[paper 36]​
2016 Stephen Brookes y Peter W. O'Hearn 2007[paper 37]​
2007[paper 38]​
2017 Cynthia Dwork, Frank McSherry, Kobbi Nissim y Adam D. Smith 2006[paper 39]​
2018 Oded Regev 2009[paper 40]​
2019 Irit Dinur 2007[paper 41]​
2020 Robin Moser y Gábor Tardos 2010[paper 42]​
2021 Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer y David Richerby 2013[paper 43]​
2013[paper 44]​
2017[paper 45]​
2022 Zvika Brakerski, Craig Gentry y Vinod Vaikuntanathan 2014[paper 46]​
2014[paper 47]​
2023 Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf y Thomas Rothvoss 2015[paper 48]​
2017[paper 49]​
2024 Ryan Williams 2011[paper 50]​
2025 David Zuckerman y Eshan Chattopadhyay 2016[paper 51]​

Artículos ganadores

  1. ↑ Babai, László; Moran, Shlomo (1988), «Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class», Journal of Computer and System Sciences 36 (2): 254-276, ISSN 0022-0000, doi:10.1016/0022-0000(88)90028-1 .
  2. ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), «The knowledge complexity of interactive proof systems», SIAM Journal on Computing 18 (1): 186-208, ISSN 1095-7111, doi:10.1137/0218012 .
  3. ↑ Håstad, Johan (1989), «Almost Optimal Lower Bounds for Small Depth Circuits», en Micali, Silvio, ed., Randomness and Computation, Advances in Computing Research 5, JAI Press, pp. 6-20, ISBN 978-0-89232-896-3, archivado desde el original el 22 de febrero de 2012 .
  4. ↑ Immerman, Neil (1988), «Nondeterministic space is closed under complementation», SIAM Journal on Computing 17 (5): 935-938, ISSN 1095-7111, doi:10.1137/0217058 .
  5. ↑ Szelepcsényi, R. (1988), «The method of forced enumeration for nondeterministic automata», Acta Informatica 26 (3): 279-284, S2CID 10838178, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489 .
  6. ↑ Sinclair, A.; Jerrum, M. (1989), «Approximate counting, uniform generation and rapidly mixing Markov chains», Information and Computation 82 (1): 93-133, ISSN 0890-5401, doi:10.1016/0890-5401(89)90067-9 .
  7. ↑ Jerrum, M.; Sinclair, Alistair (1989), «Approximating the permanent», SIAM Journal on Computing 18 (6): 1149-1178, ISSN 1095-7111, doi:10.1137/0218077 .
  8. ↑ Halpern, Joseph; Moses, Yoram (1990), «Knowledge and common knowledge in a distributed environment», Journal of the ACM 37 (3): 549-587, S2CID 52151232, arXiv:cs/0006009, doi:10.1145/79147.79161 .
  9. ↑ Toda, Seinosuke (1991), «PP is as hard as the polynomial-time hierarchy», SIAM Journal on Computing 20 (5): 865-877, ISSN 1095-7111, doi:10.1137/0220053, archivado desde el original el 3 de marzo de 2016, consultado el 8 de junio de 2010 .
  10. ↑ Shor, Peter W. (1997), «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer», SIAM Journal on Computing 26 (5): 1484-1509, ISSN 1095-7111, S2CID 2337707, arXiv:quant-ph/9508027, doi:10.1137/S0097539795293172 .
  11. ↑ Vardi, Moshe Y.; Wolper, Pierre (1994), «Reasoning about infinite computations», Information and Computation 115 (1): 1-37, ISSN 0890-5401, doi:10.1006/inco.1994.1092, archivado desde el original el 25 de agosto de 2011 .
  12. ↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), «Interactive proofs and the hardness of approximating cliques», Journal of the ACM 43 (2): 268-292, ISSN 0004-5411, doi:10.1145/226643.226652 .
  13. ↑ Arora, Sanjeev; Safra, Shmuel (1998), «Probabilistic checking of proofs: a new characterization of NP», Journal of the ACM 45 (1): 70-122, ISSN 0004-5411, S2CID 751563, doi:10.1145/273865.273901, archivado desde el original el 10 de junio de 2011 .
  14. ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), «Proof verification and the hardness of approximation problems», Journal of the ACM 45 (3): 501-555, ISSN 0004-5411, S2CID 8561542, doi:10.1145/278298.278306, archivado desde el original el 10 de junio de 2011 .
  15. ↑ Sénizergues, Géraud (2001), «L(A) = L(B)? decidability results from complete formal systems», Theor. Comput. Sci. 251 (1): 1-166, ISSN 0304-3975, doi:10.1016/S0304-3975(00)00285-1 .
  16. ↑ Freund, Y.; Schapire, R.E. (1997), «A decision-theoretic generalization of on-line learning and an application to boosting», Journal of Computer and System Sciences 55 (1): 119-139, ISSN 1090-2724, doi:10.1006/jcss.1997.1504 .
  17. ↑ Herlihy, Maurice; Shavit, Nir (1999), «The topological structure of asynchronous computability», Journal of the ACM 46 (6): 858-923, S2CID 5797174, doi:10.1145/331524.331529 .. Gödel prize lecture
  18. ↑ Saks, Michael; Zaharoglou, Fotios (2000), «Wait-free k-set agreement is impossible: The topology of public knowledge», SIAM Journal on Computing 29 (5): 1449-1483, doi:10.1137/S0097539796307698 .
  19. ↑ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), «The space complexity of approximating the frequency moments», Journal of Computer and System Sciences 58 (1): 137-147, doi:10.1006/jcss.1997.1545 .. First presented at the Symposium on Theory of Computing (STOC) in 1996.
  20. ↑ Agrawal, M.; Kayal, N.; Saxena, N. (2004), «PRIMES is in P», Annals of Mathematics 160 (2): 781-793, ISSN 0003-486X, doi:10.4007/annals.2004.160.781 .
  21. ↑ Razborov, Alexander A.; Rudich, Steven (1997), «Natural proofs», Journal of Computer and System Sciences 55 (1): 24-35, ISSN 0022-0000, doi:10.1006/jcss.1997.1494 .
  22. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2004), «Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time», J. ACM 51 (3): 385-463, ISSN 0004-5411, arXiv:math/0212413, doi:10.1145/990308.990310 .
  23. ↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), «Entropy waves, the zig-zag graph product, and new constant-degree expanders», Annals of Mathematics 155 (1): 157-187, ISSN 0003-486X, JSTOR 3062153, MR 1888797, S2CID 120739405, doi:10.2307/3062153 .
  24. ↑ Reingold, Omer (2008), «Undirected connectivity in log-space», J. ACM 55 (4): 1-24, ISSN 0004-5411, S2CID 207168478, doi:10.1145/1391289.1391291 .
  25. ↑ Arora, Sanjeev (1998), «Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems», Journal of the ACM 45 (5): 753-782, ISSN 0004-5411, S2CID 3023351, doi:10.1145/290179.290180 .
  26. ↑ Mitchell, Joseph S. B. (1999), «Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems», SIAM Journal on Computing 28 (4): 1298-1309, ISSN 1095-7111, doi:10.1137/S0097539796309764 .
  27. ↑ Håstad, Johan (2001), «Some optimal inapproximability results», Journal of the ACM 48 (4): 798-859, ISSN 0004-5411, S2CID 5120748, doi:10.1145/502090.502098 .
  28. ↑ Koutsoupias, Elias; Papadimitriou, Christos (2009). «Worst-case equilibria». Computer Science Review 3 (2): 65-69. doi:10.1016/j.cosrev.2009.04.003. 
  29. ↑ Roughgarden, Tim; Tardos, Éva (2002). «How bad is selfish routing?». Journal of the ACM 49 (2): 236-259. S2CID 207638789. doi:10.1145/506147.506153. 
  30. ↑ Nisan, Noam; Ronen, Amir (2001). «Algorithmic Mechanism Design». Games and Economic Behavior 35 (1–2): 166-196. doi:10.1006/game.1999.0790. 
  31. ↑ Boneh, Dan; Franklin, Matthew (2003). «Identity-based encryption from the Weil pairing». SIAM Journal on Computing 32 (3): 586-615. MR 2001745. doi:10.1137/S0097539701398521. 
  32. ↑ Joux, Antoine (2004). «A one round protocol for tripartite Diffie-Hellman». Journal of Cryptology 17 (4): 263-276. MR 2090557. S2CID 3350730. doi:10.1007/s00145-004-0312-y. 
  33. ↑ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). «Optimal aggregation algorithms for middleware». Journal of Computer and System Sciences 66 (4): 614-656. arXiv:cs/0204046. doi:10.1016/S0022-0000(03)00026-6. 
  34. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2011). «Spectral Sparsification of Graphs». SIAM Journal on Computing 40 (4): 981-1025. ISSN 0097-5397. S2CID 9646279. arXiv:0808.4134. doi:10.1137/08074489X. 
  35. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2013). «A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning». SIAM Journal on Computing 42 (1): 1-26. ISSN 0097-5397. S2CID 9151077. arXiv:0809.3232. doi:10.1137/080744888. 
  36. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2014). «Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems». SIAM Journal on Matrix Analysis and Applications 35 (3): 835-885. ISSN 0895-4798. S2CID 1750944. arXiv:cs/0607105. doi:10.1137/090771430. 
  37. ↑ Brookes, Stephen (2007). «A Semantics for Concurrent Separation Logic». Theoretical Computer Science 375 (1–3): 227-270. doi:10.1016/j.tcs.2006.12.034. 
  38. ↑ O'Hearn, Peter (2007). «Resources, Concurrency and Local Reasoning». Theoretical Computer Science 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. Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science 3876. Springer-Verlag. pp. 265-284. ISBN 978-3-540-32731-8. doi:10.1007/11681878_14. 
  40. ↑ Regev, Oded (2009). «On lattices, learning with errors, random linear codes, and cryptography». Journal of the ACM 56 (6): 1-40. S2CID 207156623. doi:10.1145/1568318.1568324. 
  41. ↑ Dinur, Irit (2007). «The PCP theorem by gap amplification». Journal of the ACM 54 (3): 12-es. S2CID 53244523. doi:10.1145/1236457.1236459. 
  42. ↑ «A constructive proof of the general Lovász Local Lemma». Journal of the ACM 57 (2). 2010. ISSN 0004-5411. doi:10.1145/1667053. 
  43. ↑ Bulatov, Andrei A. (2013). «The complexity of the counting constraint satisfaction problem». Journal of the ACM (Association for Computing Machinery) 60 (5): 1-41. ISSN 0004-5411. S2CID 8964233. doi:10.1145/2528400. 
  44. ↑ Dyer, Martin; Richerby, David (2013). «An Effective Dichotomy for the Counting Constraint Satisfaction Problem». SIAM Journal on Computing (Society for Industrial & Applied Mathematics (SIAM)) 42 (3): 1245-1274. ISSN 0097-5397. S2CID 1247279. arXiv:1003.3879. doi:10.1137/100811258. 
  45. ↑ Cai, Jin-Yi; Chen, Xi (22 de junio de 2017). «Complexity of Counting CSP with Complex Weights». Journal of the ACM (Association for Computing Machinery) 64 (3): 1-39. ISSN 0004-5411. S2CID 1053684. arXiv:1111.2384. doi:10.1145/2822891. 
  46. ↑ Brakerski, Zvika; Vaikuntanathan, Vinod (January 2014). «Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$». SIAM Journal on Computing 43 (2): 831-871. ISSN 0097-5397. S2CID 8831240. doi:10.1137/120868669. hdl:1721.1/115488. 
  47. ↑ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). «(Leveled) fully homomorphic encryption without bootstrapping». Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York, New York, USA: ACM Press. pp. 309-325. ISBN 9781450311151. S2CID 2602543. doi:10.1145/2090236.2090262. 
  48. ↑ Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald (2015). «Exponential Lower Bounds for Polytopes in Combinatorial Optimization». Journal of the ACM 62 (2): 17:1-17:23. S2CID 7372000. arXiv:1111.0837. doi:10.1145/2716307. 
  49. ↑ Rothvoss, Thomas (2017). «The Matching Polytope has Exponential Extension Complexity». Journal of the ACM 64 (6): 41:1-41:19. S2CID 47045361. arXiv:1311.2369. doi:10.1145/3127497. 
  50. ↑ Williams, Ryan (June 2011). «Non-uniform ACC Circuit Lower Bounds». 2011 IEEE 26th Annual Conference on Computational Complexity. IEEE. pp. 115-125. ISBN 978-1-4577-0179-5. doi:10.1109/ccc.2011.36. 
  51. ↑ Chattopadhyay, Eshan; Zuckerman, David (June 2016). «Explicit two-source extractors and resilient functions». Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. ACM. doi:10.4007/annals.2019.189.3. 

Referencias

  1. ↑ a b c «Gödel Prize». ACM Special Interest Group on Algorithms and Computation Theory. Consultado el 20 de junio de 2025. 
  2. ↑ «The Gödel Letter». Consultado el 20 de junio de 2025. 
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons Attribution-Share Alike 4.0. Pueden aplicarse cláusulas adicionales a los archivos multimedia.