Premi Gödel
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).
| Nom en la llengua original | (en) Gödel Prize  | ||
|---|---|---|---|
| Tipus | premi científic llista d'informació | ||
| Epònim | Kurt Gödel | ||
| Vigència | 1992 - | ||
| Interval de temps | 1993 - | ||
| Estat | Estats Units d'Amèrica | ||
| Guanys en premis | 5.000 $ | ||
| Conferit per | Association for Computing Machinery i European Association for Theoretical Computer Science (en)  | ||
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
- 1993 - László Babai i Shlomo Moran,[A 1] Shafi Goldwasser, Silvio Micali i Charles Rackoff,[A 2] pel desenvolupament de sistemes de demostració interactius.
- 1994 - Johan Håstad,[A 3] per trobar una cota inferior exponencial en funció de la mida de profunditat-constant d'un circuit booleà per a la funció paritat.
- 1995 - Neil Immerman[A 4] i Róbert Szelepcsényi,[A 5] pel Teorema d'Immerman-Szelepcsényi, de vinculació de classes NSPACE i co-NSPACE.
- 1996 - Mark Jerrum[A 6] i Alistair Sinclair[A 7] pel seu treball en les cadenes de Markov i l'aproximació la permanent.
- 1997 - Joseph Halpern i Yoram Moses,[A 8] pel desenvolupament del concepte de la informació en el context de sistemes distribuïts.
- 1998 - Seinosuke Toda pel seu teorema[A 9] entre classes de complexitat PP i PH.
- 1999 - Peter Shor, per l'Algoritme de Shor,[A 10] per factoritzar nombres en temps polinòmic en un computador quàntic.
- 2000 - Moshe Y. Vardi i Pierre Wolper, pel seu treball[A 11] en la lògica temporal com a part dels autòmats finits.
- 2001 - Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan i Mario Szegedypour leur théorème PCP[A 12] · [A 13] · .[A 14]
- 2002 - Géraud Sénizergues, per demostrar que l'equivalència d'autòmats de pila deterministes és decidible.[A 15]
- 2003 - Yoav Freund i Robert Schapire, per l'algoritme AdaBoost en l'aprenentatge automàtic.[A 16]
- 2004 - Maurice Herlihy, Mike Saks, Nir Shavit i Fotios Zaharoglou, per aplicar topologia a la teoria de computació distribuïda[A 17] · .[A 18]
- 2005 - Noga Alon, Yossi Matias i Mario Szegedy per les seves contribucions[A 19] en els algoritmes de mineria de fluxos de dades.
- 2006 - Manindra Agrawal, Neeraj Kayal, Nitin Saxena, pel Test de primalitat AKS.[A 20]
- 2007 - Alexander Razborov i Steven Rudich, per les demostracions naturals.[A 21]
- 2008 - Shanghua Teng i Daniel Spielman, per l'anàlisi Smoothed de logaritmes.[A 22]
- 2009 - Omer Reingold, Avi Wigderson i Salil Vadhan, per l'anàlisi d'SL (complexitat)[A 23] · .[A 24]
- 2010 - Sanjeev Arora i Joseph S. B. Mitchell per l'esquema d'aproximació polinòmica del problema del viatjant de comerç[A 25] · [A 26] en el cas euclidiana.
- 2011 - Johan Håstad, per resultats de dificultat d'aproximació, relacionat amb el teorema PCP.[A 27]
- 2012 - Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden i Éva Tardos,
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
- ↑ 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].
- ↑ 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].
- ↑ 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.
- ↑ 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.
- ↑ Szelepcsényi, R. «The method of forced enumeration for nondeterministic automata». Acta Informatica, 26, 3, 1988, pàg. 279–284. DOI: 10.1007/BF00299636.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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]
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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]
- ↑ 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]
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Håstad, Johan «Some optimal inapproximability results». Journal of the ACM, 48, 2001, pàg. Pàg. 798–859. DOI: 10.1145/502090.502098.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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 |
- Prix Gödel en l'EATCS
- Prix Gödel en SIGACT