Prêmio Gödel

O Prêmio Gödel é um prêmio por artigos de destaque em teoria da ciência da computação, homenageando Kurt Gödel e concedido conjuntamente pela Associação Europeia de Ciência Computacional Teórica (EATCS) e pela ACM SIGACT.

O prêmio é concedido anualmente desde 1993. Seu valor monetário é de 5 mil dólares. O prêmio é concedido durante o "Simpósio sobre Teoria da Computação" ou durante o "Colóquio Internacional sobre Autômatos, Linguagem e Programação". Para ser elegível ao prêmio, um artigo deve ter sido publicado em uma revista especializada com revisores nos 14 anos precedentes. Anteriormente o tempo era de 7 anos.

Laureados

Ano Laureado Notas Ano de publicação
1993 László Babai, Shafrira Goldwasser, Silvio Micali, Shlomo Moran e Charles Rackoff pelo desenvolvimento de sistemas de prova interativa 1988,[artigo 1] 1989[artigo 2]
1994 Johan Håstad por uma demonstração sobre as dimensões dos circuitos boolianos. 1989[artigo 3]
1995 Neil Immerman e Róbert Szelepcsényi pelo Teorema de Immerman–Szelepcsényi, referente à complexidade não determinística do espaço. 1988,[artigo 4] 1988[artigo 5]
1996 Mark Jerrum e Alistair Sinclair por um trabalho sobre as cadeias de Markov e sobre a aproximação do permanente de uma matriz. 1989,[artigo 6] 1989[artigo 7]
1997 Joseph Halpern e Yoram Moses por definir uma noção formal de "conhecimento" em ambientes distribuídos. 1990[artigo 8]
1998 Seinosuke Toda 1991[artigo 9]
1999 Peter Shor 1997[artigo 10]
2000 Moshe Y. Vardi e Pierre Wolper 1994[artigo 11]
2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan e Mario Szegedy 1996,[artigo 12] 1998,[artigo 13] 1998[artigo 14]
Géraud Sénizergues 2001[artigo 15]
2003 Yoav Freund e Robert Schapire 1997[artigo 16]
2004 Maurice Herlihy, Michael Saks, Nir Shavit e Fotios Zaharoglou 1999,[artigo 17] 2000[artigo 18]
2005 Noga Alon, Yossi Matias e Mario Szegedy 1999[artigo 19]
2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena 2004[artigo 20]
2007 Alexander Razborov, Steven Rudich 1997[artigo 21]
2008 Daniel Spielman, Shanghua Teng 2004[artigo 22]
2009 Omer Reingold, Salil Vadhan, Avi Wigderson 2002,[artigo 23] 2008[artigo 24]
2010 Sanjeev Arora, Joseph Shannon Baird Mitchell 1998,[artigo 25]

1999[artigo 26]

2011 Johan Håstad 2001[paper 1]
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden e Éva Tardos 2009,[paper 2] 2002,[paper 3] 2001[paper 4]
2013 Dan Boneh, Matthew K. Franklin e Antoine Joux 2003,[paper 5]

2004[paper 6]

2014 Ronald Fagin, Amnon Lotem e Moni Naor 2003,[paper 7]
2015 Daniel Spielman, Shanghua Teng 2011[paper 8]

2013[paper 9] 2014[paper 10]

2016 Stephen Brookes e Peter O'Hearn 2007, 2007
2017[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim e Adam D. Smith 2006[paper 11]
2018[2] Oded Regev 2009[paper 12]
2019[3] Irit Dinur 2007[paper 13]

Referências

  1. ↑ Babai, László; Moran, Shlomo (1988), «Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class» (PDF), Boston, MA: Academic Press, Journal of Computer and System Sciences, ISSN 0022-0000, 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1 
  2. ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), «The knowledge complexity of interactive proof systems» (PDF), Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 18 (1): 186–208, doi:10.1137/0218012 
  3. ↑ Håstad, Johan (1989), «Almost Optimal Lower Bounds for Small Depth Circuits», in: Micali, Silvio, Cópia arquivada (PDF), ISBN 0892328967, Advances in Computing Research, 5, JAI Press, pp. 6–20, consultado em 30 de setembro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  4. ↑ Immerman, Neil (1988), «Nondeterministic space is closed under complementation» (PDF), Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 17 (5): 935–938, doi:10.1137/0217058 
  5. ↑ Szelepcsényi, R. (1988), «The method of forced enumeration for nondeterministic automata», Springer-Verlag New York, Inc., Acta Informatica, 26 (3): 279–284, doi:10.1007/BF00299636 
  6. ↑ Sinclair, A.; Jerrum, M. (1989), «Approximate counting, uniform generation and rapidly mixing Markov chains», Elsevier, Information and Computation, ISSN 0890-5401, 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9 
  7. ↑ Jerrum, M.; Sinclair, Alistair (1989), «Approximating the permanent», Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 18 (6): 1149–1178, 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, doi:10.1145/79147.79161 
  9. ↑ Toda, Seinosuke (1991), «PP is as hard as the polynomial-time hierarchy» (PDF), Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 20 (5): 865–877, doi:10.1137/0220053 
  10. ↑ Shor, Peter W. (1997), «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer» (PDF), Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 26 (5): 1484–1509, doi:10.1137/S0097539795293172 [ligação inativa]
  11. ↑ Vardi, Moshe Y.; Wolper, Pierre (1994), «Cópia arquivada» (PDF), Boston, MA: Academic Press, Information and Computation, ISSN 0890-5401, 115 (1): 1–37, doi:10.1006/inco.1994.1092, consultado em 30 de setembro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  12. ↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), «Interactive proofs and the hardness of approximating cliques» (PDF), ACM, Journal of the ACM, ISSN 0004-5411, 43 (2): 268–292, doi:10.1145/226643.226652 
  13. ↑ Arora, Sanjeev; Safra, Shmuel (1998), «Cópia arquivada» (PDF), ACM, Journal of the ACM, ISSN 0004-5411, 45 (1): 70–122, doi:10.1145/273865.273901, consultado em 30 de setembro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  14. ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), «Cópia arquivada» (PDF), ACM, Journal of the ACM, ISSN 0004-5411, 45 (3): 501–555, doi:10.1145/278298.278306, consultado em 30 de setembro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  15. ↑ Sénizergues, Géraud (2001), «L(A) = L(B)? decidability results from complete formal systems», Essex, UK: Elsevier Science Publishers Ltd., Theor. Comput. Sci., ISSN 0304-3975, 251 (1): 1–166, 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» (PDF), Elsevier, Journal of Computer and System Sciences, ISSN 1090-2724, 55 (1): 119–139, doi:10.1006/jcss.1997.1504 
  17. ↑ Herlihy, Maurice; Shavit, Nir (1999), «The topological structure of asynchronous computation» (PDF), Journal of the ACM, 46 (6): 858–923, 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» (PDF), 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), «Cópia arquivada» (PDF), Annals of Mathematics, ISSN 0003-486X, 160: 781–793, doi:10.4007/annals.2004.160.781, consultado em 30 de setembro de 2010, cópia arquivada (PDF) em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  21. ↑ Razborov, Alexander A.; Rudich, Steven (1997), «Natural proofs», Boston, MA: Academic Press, Journal of Computer and System Sciences, ISSN 0022-0000, 55 (1): 24–35, doi:10.1006/jcss.1997.1494, Predefinição:ECCC 
  22. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2004), «Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time» (PDF), ACM, J. ACM, ISSN 0004-5411, 51 (3): 385–463 [ligação inativa]
  23. ↑ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), «Entropy waves, the zig-zag graph product, and new constant-degree expanders» (PDF), Annals of Mathematics, Annals of Mathematics, ISSN 0003-486X, 155 (1): 157–187, JSTOR 10.2307/3062153, doi:10.2307/3062153, MR1888797 [ligação inativa]
  24. ↑ Reingold, Omer (2008), «Cópia arquivada», ACM, J. ACM, ISSN 0004-5411, 55 (4): 1–24, consultado em 30 de setembro de 2010, cópia arquivada em |arquivourl= requer |arquivodata= (ajuda) 🔗 
  25. ↑ Arora, Sanjeev (1998), «Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems», ACM, Journal of the ACM, ISSN 0004-5411, 45 (5): 753–782, 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», Philadelphia: Society for Industrial and Applied Mathematics, SIAM Journal on Computing, ISSN 1095-7111, 28 (4): 1298–1309, doi:10.1137/S0097539796309764 
  1. ↑ Håstad, Johan (2001), «Some optimal inapproximability results» (PDF), ACM, Journal of the ACM, ISSN 0004-5411, 48: 798–859, doi:10.1145/502090.502098 
  2. ↑ Koutsoupias, Elias; Papadimitriou, Christos (2009). «Worst-case equilibria». Computer Science Review. 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003 
  3. ↑ Roughgarden, Tim; Tardos, Éva (2002). «How bad is selfish routing?». Journal of the ACM. 49 (2): 236–259. doi:10.1145/506147.506153 
  4. ↑ Nisan, Noam; Ronen, Amir (2001). «Algorithmic Mechanism Design». Games and Economic Behavior. 35 (1-2): 166–196. doi:10.1006/game.1999.0790 
  5. ↑ 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 
  6. ↑ Joux, Antoine (2004). «A one round protocol for tripartite Diffie-Hellman». Journal of Cryptology. 17 (4): 263–276. MR 2090557. doi:10.1007/s00145-004-0312-y 
  7. ↑ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). «Optimal aggregation algorithms for middleware». Journal of Computer and System Sciences. 66 (4): 614–656. doi:10.1016/S0022-0000(03)00026-6 
  8. ↑ Spielman, Daniel A.; Teng, Shang-Hua (2011). «Spectral Sparsification of Graphs». SIAM Journal on Computing. 40 (4): 981–1025. ISSN 0097-5397. doi:10.1137/08074489X 
  9. ↑ 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. doi:10.1137/080744888 
  10. ↑ 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. doi:10.1137/090771430 
  11. ↑ 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 
  12. ↑ Regev, Oded (2009). «On lattices, learning with errors, random linear codes, and cryptography». Journal of the ACM. 56 (6): 1–40. CiteSeerX 10.1.1.215.3543Acessível livremente. doi:10.1145/1568318.1568324 
  13. ↑ Dinur, Irit (2007). «The PCP theorem by gap amplification». Journal of the ACM. 54 (3) 

Ligações externas

  1. ↑ [https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel- prize «2017 Gödel Prize»] Verifique valor |url= (ajuda). European Association for Theoretical Computer Science. EATCS. Consultado em 29 de março de 2017  line feed character character in |url= at position 82 (ajuda)
  2. ↑ «2018 Gödel Prize citation» 
  3. ↑ «2019 Gödel Prize citation»