Premi Gödel
| 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 é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]- 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. Arxivat de l'original el 2011-06-10. DOI: 10.1145/226643.226652 [Consulta: 6 abril 2014].
- ↑ 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