Premi Gödel

De Viquipèdia
Jump to navigation Jump to search
Infotaula de premiPremi Gödel
Tipus premi
Epònim Kurt Gödel
Concedit per Association for Computing Machinery i European Association for Theoretical Computer Science Tradueix
Inici 1992
Modifica les dades a Wikidata

El Premi Gödel és un premi que es lliura a autors d'articles relacionats amb la teoria de la computació. El nom del premi es deu al matemàtic Kurt Gödel, i és atorgat per l'Associació Europea per a la Informàtica Teòrica (EATCS) i el Grup d'Interès Especial d'Algorismes i Teoria de la Computació de l'Association for Computing Machinery (ACM).

El Premi Gödel es lliura anualment des de 1993, ja sigui en l'STOC (ACM Symposium on Theory of Computing), una de les principals conferències dels Estats Units en l'àrea d'informàtica teòrica, o bé en l'ICALP (International Colloquium on Automata, Languages​​, and Programming), una de les principals conferències europees a la mateixa àrea. A part de la distinció, inclou un bo de 5000 dòlars. Com a requisit per rebre el premi, l'article guanyador ha d'haver estat publicat en una revista científica un màxim de 14 anys enrere (anteriorment n'eren només 7 anys).

Guanyadors[modifica]

per a la creació de la teoria algorísmica dels jocs (a mig camí entre l'algorísmica i la teoria dels jocs)[A 28] · [A 29] · .[A 30]

per a la introducció i l'ús del concepte d'acoblament (en anglès) a criptografia[A 31] · .[A 32]

Articles distingits[modifica]

  1. Babai, László; Moran, Shlomo «Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class». Journal of Computer and System Sciences, 36, 2, 1988, pàg. Pàg. 254–276. DOI: 10.1016/0022-0000(88)90028-1.
  2. Goldwasser, S.; Micali, S.; Rackoff, C. «The knowledge complexity of interactive proof systems». SIAM Journal on Computing, 18, 1, 1989, pàg. Pàg.186–208. DOI: 10.1137/0218012.
  3. Håstad, Johan. «Almost Optimal Lower Bounds for Small Depth Circuits». A: Randomness and Computation, 1989, p. Pàg. 6–20 (Advances in Computing Research). ISBN 0-89232-896-7. 
  4. Immerman, Neil «Nondeterministic space is closed under complementation». SIAM Journal on Computing, 17, 5, 1988, pàg. 935–938. DOI: 10.1137/0217058. ISSN: 1095-7111.
  5. Szelepcsényi, R. «The method of forced enumeration for nondeterministic automata». Acta Informatica, 26, 3, 1988, pàg. 279–284. DOI: 10.1007/BF00299636.
  6. Jerrum, Mark; Sinclair, Alistair «Approximating the permanent». SIAM Journal on Computing, 18, 6, 1989, pàg. Pàg. 1149–1178. DOI: 10.1137/0218077. ISSN: 1095-7111.
  7. Sinclair, Alistair; Jerrum, Mark «Approximate counting, uniform generation and rapidly mixing Markov chains». Information and Computation, 82, 1, 1989, pàg. Pàg. 93–133. DOI: 10.1016/0890-5401(89)90067-9.
  8. Halpern, Joseph; Moses, Yoram «Knowledge and common knowledge in a distributed environment». Journal of the ACM, 37, 3, 1990, pàg. Pàg. 549–587. DOI: 10.1145/79147.79161.
  9. Toda, Seinosuke «PP is as hard as the polynomial-time hierarchy». SIAM Journal on Computing, 20, 5, 1991, pàg. Pàg. 865–877. DOI: 10.1137/0220053.
  10. Shor, Peter W. «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer». SIAM Journal on Computing, 26, 5, 1997, pàg. Pàg. 1484–1509. DOI: 10.1137/S0097539795293172.
  11. Vardi, Moshe Y.; Wolper, Pierre «Reasoning about infinite computations». Information and Computation, 115, 1, 1994, pàg. Pàg. 1–37. DOI: 10.1006/inco.1994.1092.
  12. Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario «Interactive proofs and the hardness of approximating cliques». Journal of the ACM, 43, 2, 1996, pàg. Pàg. 268–292. DOI: 10.1145/226643.226652.
  13. Arora, Sanjeev; Safra, Shmuel «Probabilistic checking of proofs: a new characterization of NP». Journal of the ACM, 45, 1, 1998, pàg. Pàg. 70–122. DOI: 10.1145/273865.273901.
  14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario «Proof verification and the hardness of approximation problems». Journal of the ACM, 45, 3, 1998, pàg. Pàg. 501–555. DOI: 10.1145/278298.278306.
  15. Sénizergues, Géraud «L(A) = L(B)? decidability results from complete formal systems». Theor. Comput. Sci., 251, 1, 2001, pàg. Pàg. 1–166. DOI: 10.1016/S0304-3975(00)00285-1.
  16. Freund, Y.; Schapire, R.E. «A decision-theoretic generalization of on-line learning and an application to boosting». Journal of Computer and System Sciences, 55, 1, 1997, pàg. Pàg. 119–139. DOI: 10.1006/jcss.1997.1504.
  17. Herlihy, Maurice; Shavit, Nir «The topological structure of asynchronous computation». Journal of the ACM, 46, 6, 1999, pàg. Pàg. 858–923. DOI: 10.1145/331524.331529.
  18. Saks, Michael; Zaharoglou, Fotios «Wait-free k-set agreement is impossible: The topology of public knowledge». SIAM Journal on Computing, 29, 5, 2000, pàg. Pàg. 1449–1483. DOI: 10.1137/S0097539796307698.
  19. Alon, Noga; Matias, Yossi; Szegedy, Mario «The space complexity of approximating the frequency moments». Journal of Computer and System Sciences, 58, 1, 1999, pàg. Pàg. 137–147. DOI: 10.1006/jcss.1997.1545.
  20. Agrawal, M.; Kayal, N.; Saxena, N. «PRIMES is in P». Annals of Mathematics, 160, 2, 2004, pàg. Pàg. 781–793. DOI: 10.4007/annals.2004.160.781.
  21. Razborov, Alexander A.; Rudich, Steven «Natural proofs». Journal of Computer and System Sciences, 55, 1, 1997, pàg. Pàg. 24–35. DOI: 10.1006/jcss.1997.1494. Plantilla:ECCC.
  22. Spielman, Daniel A.; Teng, Shang-Hua «Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time». Journal of the ACM, 51, 3, 2004, pàg. Pàg. 385–463.
  23. Reingold, Omer; Vadhan, Salil; Wigderson, Avi «Entropy waves, the zig-zag graph product, and new constant-degree expanders». Annals of Mathematics, 155, 1, 2002, pàg. 157–187. DOI: 10.2307/3062153. JSTOR: 3062153.
  24. Reingold, Omer «Undirected connectivity in log-space». Journal of the ACM, 55, 4, 2008, pàg. 1–24.
  25. Arora, Sanjeev «Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems». Journal of the ACM, 45, 5, 1998, pàg. Pàg. 753–782. DOI: 10.1145/290179.290180.
  26. Mitchell, Joseph S. B. «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, 1999, pàg. 1298–1309. DOI: 10.1137/S0097539796309764. ISSN: 1095-7111.
  27. Håstad, Johan «Some optimal inapproximability results». Journal of the ACM, 48, 2001, pàg. Pàg. 798–859. DOI: 10.1145/502090.502098.
  28. Koutsoupias, Elias; Papadimitriou, Christos «Worst-case equilibria». Computer Science Review, 3, 2, 2009, pàg. Pàg. 65–69. DOI: 10.1016/j.cosrev.2009.04.003.
  29. Roughgarden, Tim; Tardos, Éva «How bad is selfish routing?». Journal of the ACM, 49, 2, 2002, pàg. Pàg. 236–259. DOI: 10.1145/506147.506153.
  30. Nisan, Noam; Ronen, Amir «Algorithmic Mechanism Design». Games and Economic Behavior, 35, 1-2, 2001, pàg. Pàg. 166–196. DOI: 10.1006/game.1999.0790.
  31. Boneh, Dan; Franklin, Matthew «Identity-based encryption from the Weil pairing». SIAM Journal on Computing, 32, 3, 2003, pàg. Pàg. 586–615. DOI: 10.1137/S0097539701398521.
  32. Joux, Antoine «A one round protocol for tripartite Diffie-Hellman». Journal of Cryptology, 17, 4, 2004, pàg. Pàg. 263–276. DOI: 10.1007/s00145-004-0312-y.

Referències[modifica]

Vegeu també[modifica]

Enllaços externs[modifica]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Premi Gödel Modifica l'enllaç a Wikidata