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.

LaureadosEditar

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 pelo teorema de Toda "which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)" 1991[artigo 9]
1999 Peter Shor pelo algoritmo de Shor for factoring numbers in polynomial time on a quantum computer 1997[artigo 10]
2000 Moshe Y. Vardi e Pierre Wolper for work on model checking with finite automata 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 for the PCP theorem and its applications to hardness of approximation 1996,[artigo 12] 1998,[artigo 13] 1998[artigo 14]
2002 Géraud Sénizergues for proving that equivalence of deterministic pushdown automata is decidable 2001[artigo 15]
2003 Yoav Freund e Robert Schapire for the AdaBoost algorithm 1997[artigo 16]
2004 Maurice Herlihy, Michael Saks, Nir Shavit e Fotios Zaharoglou for applications of topology to the theory of distributed computing 1999,[artigo 17] 2000[artigo 18]
2005 Noga Alon, Yossi Matias e Mario Szegedy for their foundational contribution to streaming algorithms 1999[artigo 19]
2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena for the AKS primality test 2004[artigo 20]
2007 Alexander Razborov, Steven Rudich for natural proofs 1997[artigo 21]
2008 Daniel Spielman, Shanghua Teng for smoothed analysis of algorithms 2004[artigo 22]
2009 Omer Reingold, Salil Vadhan, Avi Wigderson for zig-zag product of graphs and undirected connectivity in log space 2002,[artigo 23] 2008[artigo 24]
2010 Sanjeev Arora, Joseph Shannon Baird Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) 1998,[artigo 25]

1999[artigo 26]

2011 Johan Håstad for proving optimal inapproximability result for various combinatorial problems 2001[paper 1]
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden e Éva Tardos for laying the foundations of algorithmic game theory[1] 2009,[paper 2] 2002,[paper 3] 2001[paper 4]
2013 Dan Boneh, Matthew K. Franklin e Antoine Joux for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[2] 2003,[paper 5]

2004[paper 6]

2014 Ronald Fagin, Amnon Lotem e Moni Naor for Optimal Aggregation Algorithms for Middleware[3] 2003,[paper 7]
2015 Daniel Spielman, Shanghua Teng for their series of papers on nearly-linear-time Laplacian solvers[4]

2011[paper 8] 2013[paper 9] 2014[paper 10]

2016 Stephen Brookes e Peter O'Hearn for their invention of Concurrent Separation Logic 2007, 2007
2017[5] Cynthia Dwork, Frank McSherry, Kobbi Nissim e Adam D. Smith for the invention of differential privacy 2006[paper 11]
2018[6] Oded Regev for introducing the Learning with errors problem 2009[paper 12]
2019[7] Irit Dinur for her new proof of the PCP Theorem by gap amplification 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, Randomness and Computation (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) 🔗  |title= e |título= redundantes (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), «Reasoning about infinite computations» (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) 🔗  |title= e |título= redundantes (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), «Probabilistic checking of proofs: a new characterization of NP» (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) 🔗  |title= e |título= redundantes (ajuda)
  14. ↑ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), «Proof verification and the hardness of approximation problems» (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) 🔗  |title= e |título= redundantes (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), «PRIMES is in P» (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) 🔗  |title= e |título= redundantes (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), «Undirected connectivity in log-space», 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) 🔗  |title= e |título= redundantes (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 

Ligações externasEditar



Erro de citação: Existem etiquetas <ref> para um grupo chamado "paper", mas não foi encontrada nenhuma etiqueta <references group="paper"/> correspondente

  1. ↑ «Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory». 16 de maio de 2012. Consultado em 16 de maio de 2012 
  2. ↑ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Arquivado em 1 de junho de 2013, no Wayback Machine., Association for Computing Machinery, May 29, 2013.
  3. ↑ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
  4. ↑ [https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf Arquivado em 9 de dezembro de 2017, no Wayback Machine. 2015 Gödel Prize Association for Computing Machinery announcement.
  5. ↑ [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 March 2017  line feed character character in |url= at position 82 (ajuda); Verifique data em: |acessodata= (ajuda)
  6. ↑ «2018 Gödel Prize citation» 
  7. ↑ «2019 Gödel Prize citation» 
Obtida de "https://pt.wikipedia.org/w/index.php?title=Prêmio_Gödel&oldid=56788032"