Prêmio Gödel
Este artigo ou se(c)ção está a ser traduzido |
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
Este artigo ou se(c)ção está a ser traduzido |
Referências
- ↑ 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
- ↑ 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
- ↑ 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) - ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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]
- ↑ 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) - ↑ 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
- ↑
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) - ↑ 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) - ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ 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) - ↑ 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
- ↑ 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]
- ↑ 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]
- ↑ 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) - ↑ 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
- ↑ 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
- «Página oficial» (em inglês)
Erro de citação: Existem etiquetas <ref>
para um grupo chamado "paper", mas não foi encontrada nenhuma etiqueta <references group="paper"/>
correspondente
- ↑ «Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory». 16 de maio de 2012. Consultado em 16 de maio de 2012
- ↑ 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.
- ↑ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
- ↑ [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.
- ↑ [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) - ↑ «2018 Gödel Prize citation»
- ↑ «2019 Gödel Prize citation»