Prêmio Gödel

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de en:Gödel Prize. Ajude e colabore com a tradução.

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[editar | editar código-fonte]

Ano Laureado Notas Ano de publicação
1993 László Babai, Shafrira Goldwasser, Silvio Micali, Shlomo Moran e Charles Rackoff for the development of interactive proof systems 1988[artigo 1] , 1989[artigo 2]
1994 Johan Håstad for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function). 1989[artigo 3]
1995 Neil Immerman e Róbert Szelepcsényi for the Immerman-Szelepcsényi theorem regarding nondeterministic space complexity 1988[artigo 4] , 1988[artigo 5]
1996 Mark Jerrum e Alistair Sinclair for work on Markov chains e the approximation of the permanent 1989[artigo 6] , 1989[artigo 7]
1997 Joseph Halpern e Yoram Moses for defining a formal notion of "knowledge" in distributed environments 1990[artigo 8]
1998 Seinosuke Toda for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH) 1991[artigo 9]
1999 Peter Shor for Shor's algorithm 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 S. B. 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]

Referências

  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 (Boston, MA: Academic Press) 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf 
  2. Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf 
  3. Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 0892328967, http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf 
  4. Immerman, Neil (1988), "Nondeterministic space is closed under complementation", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111, http://www.cs.umass.edu/~immerman/pub/space.pdf 
  5. Szelepcsényi, R. (1988), "The method of forced enumeration for nondeterministic automata", Acta Informatica (Springer-Verlag New York, Inc.) 26 (3): 279–284, doi:10.1007/BF00299636 
  6. Sinclair, A.; Jerrum, M. (1989), "Approximate counting, uniform generation and rapidly mixing Markov chains", Information and Computation (Elsevier) 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9, ISSN 0890-5401 
  7. Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (6): 1149–1178, doi:10.1137/0218077, ISSN 1095-7111 
  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", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111, http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf 
  10. Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 26 (5): 1484–1509, doi:10.1137/S0097539795293172, ISSN 1095-7111, http://physics.princeton.edu/~mcdonald/examples/QM/shor_siamjc_26_1484_97.pdf 
  11. Vardi, Moshe Y.; Wolper, Pierre (1994), "Reasoning about infinite computations", Information and Computation (Boston, MA: Academic Press) 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf 
  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 (ACM) 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411, http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf 
  13. Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP", Journal of the ACM (ACM) 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, http://www.cs.umd.edu/~gasarch/pcp/AS.pdf 
  14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM (ACM) 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf 
  15. Sénizergues, Géraud (2001), "L(A) = L(B)? decidability results from complete formal systems", Theor. Comput. Sci. (Essex, UK: Elsevier Science Publishers Ltd.) 251 (1): 1–166, doi:10.1016/S0304-3975(00)00285-1, ISSN 0304-3975 
  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 (Elsevier) 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724, http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf 
  17. Herlihy, Maurice; Shavit, Nir (1999), "The topological structure of asynchronous computation", Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529, http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf . 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, http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf . 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: 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, http://math.berkeley.edu/~coleman/Courses/Fall08/Cryptography/primality_v6.pdf 
  21. Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences (Boston, MA: Academic Press) 55 (1): 24–35, doi:10.1006/jcss.1997.1494, Predefinição:ECCC, ISSN 0022-0000 
  22. Spielman, Daniel A.; Teng, Shang-Hua (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", J. ACM (ACM) 51 (3): 385–463, ISSN 0004-5411, http://eprints.kfupm.edu.sa/65442/1/65442.pdf 
  23. Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy waves, the zig-zag graph product, and new constant-degree expanders", Annals of Mathematics (Annals of Mathematics) 155 (1): 157–187, doi:10.2307/3062153, MR1888797, ISSN 0003-486X, http://eprints.kfupm.edu.sa/37801/1/37801.pdf 
  24. Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM (ACM) 55 (4): 1–24, ISSN 0004-5411, http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps 
  25. Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM (ACM) 45 (5): 753–782, doi:10.1145/290179.290180, ISSN 0004-5411 
  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 (Philadelphia: Society for Industrial and Applied Mathematics) 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111 

Ligações externas[editar | editar código-fonte]