Vés al contingut

Premi Gödel

De la Viquipèdia, l'enciclopèdia lliure
Plantilla:Infotaula esdevenimentPremi Gödel
Nom en la llengua original(en) Gödel Prize Modifica el valor a Wikidata
Tipuspremi científic
llista d'informació Modifica el valor a Wikidata
EpònimKurt Gödel Modifica el valor a Wikidata
Vigència1992 Modifica el valor a Wikidata - 
Interval de temps1993 Modifica el valor a Wikidata - 
EstatEstats Units d'Amèrica Modifica el valor a Wikidata
Guanys en premis5.000 $ Modifica el valor a Wikidata
Conferit perAssociation for Computing Machinery i European Association for Theoretical Computer Science (en) Tradueix Modifica el valor 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. Arxivat de l'original el 2011-07-06. DOI: 10.1016/0022-0000(88)90028-1 [Consulta: 6 abril 2014].
  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. Arxivat de l'original el 2011-09-27. DOI: 10.1137/0218012 [Consulta: 6 abril 2014].
  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. Arxivat de l'original el 2016-03-03. DOI: 10.1137/0220053 [Consulta: 6 abril 2014]. Arxivat 2016-03-03 a Wayback Machine.
  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.[Enllaç no actiu]
  11. Vardi, Moshe Y.; Wolper, Pierre «Reasoning about infinite computations». Information and Computation, 115, 1, 1994, pàg. Pàg. 1–37. Arxivat de l'original el 2011-08-25. DOI: 10.1006/inco.1994.1092 [Consulta: 6 abril 2014]. Arxivat 2011-08-25 a Wayback Machine.
  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. Arxivat de l'original el 2011-06-10. DOI: 10.1145/226643.226652 [Consulta: 6 abril 2014].
  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. Arxivat de l'original el 2011-06-10. DOI: 10.1145/273865.273901 [Consulta: 6 abril 2014]. Arxivat 2011-06-10 a Wayback Machine.
  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. Arxivat de l'original el 2011-06-10. DOI: 10.1145/278298.278306 [Consulta: 6 abril 2014]. Arxivat 2011-06-10 a Wayback Machine.
  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. Arxivat de l'original el 2011-06-07. DOI: 10.4007/annals.2004.160.781 [Consulta: 6 abril 2014]. Arxivat 2011-06-07 a Wayback Machine.
  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.[Enllaç no actiu]
  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.[Enllaç no actiu]
  24. Reingold, Omer «Undirected connectivity in log-space». Journal of the ACM, 55, 4, 2008, pàg. 1–24. Arxivat de l'original el 2011-06-12 [Consulta: 6 abril 2014]. Arxivat 2011-06-12 a Wayback Machine.
  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]