Prix Gödel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : Navigation, rechercher

Nommé en l'honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l'European Association for Theoretical Computer Science (EATCS) et Pôle Algorithmique et Informatique théorique de l'ACM (SIGACT) de l'Association for Computing Machinery (ACM) pour honorer des travaux remarquables d'informatique théorique.

Le Prix Gödel est attribué annuellement depuis 1993 et comporte une récompense de 5 000 USD. Le prix distingue un article, plutôt qu'un individu. Pour être éligible, l'article du récipiendaire doit avoir été publié dans un journal avec comité de lecture dans les 14 années précédentes[1].

Sommaire

Lauréats [modifier]

Articles distingués [modifier]

  1. ↑ László Babai et Shlomo Moran, « Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class », Journal of Computer and System Sciences, vol. 36, no 2, 1988, p. 254–276 [texte intégral, lien DOI] 
  2. ↑ S. Goldwasser, S. Micali et C. Rackoff, « The knowledge complexity of interactive proof systems », SIAM Journal on Computing, vol. 18, no 1, 1989, p. 186–208 [texte intégral, lien DOI] 
  3. ↑ Johan Håstad, « Almost Optimal Lower Bounds for Small Depth Circuits », dans Silvio Micali (éditeur), Randomness and Computation, JAI Press, coll. « Advances in Computing Research » (no 5), 1989 (ISBN 0-89232-896-7) [lire en ligne], p. 6–20 
  4. ↑ Neil Immerman, « Nondeterministic space is closed under complementation », SIAM Journal on Computing, vol. 17, no 5, 1988, p. 935–938 (ISSN 1095-7111) [texte intégral, lien DOI] 
  5. ↑ R. Szelepcsényi, « The method of forced enumeration for nondeterministic automata », Acta Informatica, vol. 26, no 3, 1988, p. 279–284 [lien DOI] 
  6. ↑ Mark Jerrum et Alistair Sinclair, « Approximating the permanent », SIAM Journal on Computing, vol. 18, no 6, 1989, p. 1149–1178 (ISSN 1095-7111) [lien DOI] 
  7. ↑ Alistair Sinclair et Mark Jerrum, « Approximate counting, uniform generation and rapidly mixing Markov chains », Information and Computation, vol. 82, no 1, 1989, p. 93–133 [lien DOI] 
  8. ↑ Joseph Halpern et Yoram Moses, « Knowledge and common knowledge in a distributed environment », Journal of the ACM, vol. 37, no 3, 1990, p. 549–587 [lien DOI] 
  9. ↑ Seinosuke Toda, « PP is as hard as the polynomial-time hierarchy », SIAM Journal on Computing, vol. 20, no 5, 1991, p. 865–877 [texte intégral, lien DOI] 
  10. ↑ Peter W. Shor, « Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer », SIAM Journal on Computing, vol. 26, no 5, 1997, p. 1484–1509 [texte intégral, lien DOI] 
  11. ↑ Moshe Y. Vardi et Pierre Wolper, « Reasoning about infinite computations », Information and Computation, vol. 115, no 1, 1994, p. 1–37 [texte intégral, lien DOI] 
  12. ↑ Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra et Mario Szegedy, « Interactive proofs and the hardness of approximating cliques », Journal of the ACM, vol. 43, no 2, 1996, p. 268–292 [texte intégral, lien DOI] 
  13. ↑ Sanjeev Arora et Shmuel Safra, « Probabilistic checking of proofs: a new characterization of NP », Journal of the ACM, vol. 45, no 1, 1998, p. 70–122 [texte intégral, lien DOI] 
  14. ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan et Mario Szegedy, « Proof verification and the hardness of approximation problems », Journal of the ACM, vol. 45, no 3, 1998, p. 501–555 [texte intégral, lien DOI] 
  15. ↑ Géraud Sénizergues, « L(A) = L(B)? decidability results from complete formal systems », Theor. Comput. Sci., vol. 251, no 1, 2001, p. 1–166 [lien DOI] 
  16. ↑ Y. Freund et R.E. Schapire, « A decision-theoretic generalization of on-line learning and an application to boosting », Journal of Computer and System Sciences, vol. 55, no 1, 1997, p. 119–139 [texte intégral, lien DOI] 
  17. ↑ Maurice Herlihy et Nir Shavit, « The topological structure of asynchronous computation », Journal of the ACM, vol. 46, no 6, 1999, p. 858–923 [texte intégral, lien DOI] 
  18. ↑ Michael Saks et Fotios Zaharoglou, « Wait-free k-set agreement is impossible: The topology of public knowledge », SIAM Journal on Computing, vol. 29, no 5, 2000, p. 1449–1483 [lien DOI] 
  19. ↑ Noga Alon, Yossi Matias et Mario Szegedy, « The space complexity of approximating the frequency moments », Journal of Computer and System Sciences, vol. 58, no 1, 1999, p. 137–147 [texte intégral, lien DOI] 
  20. ↑ M. Agrawal, N. Kayal et N. Saxena, « PRIMES is in P », Annals of Mathematics, vol. 160, no 2, 2004, p. 781–793 [texte intégral, lien DOI] 
  21. ↑ Alexander A. Razborov et Steven Rudich, « Natural proofs », Journal of Computer and System Sciences, vol. 55, no 1, 1997, p. 24–35 [lien DOI] 
  22. ↑ Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time », Journal of the ACM, vol. 51, no 3, 2004, p. 385–463 [texte intégral] 
  23. ↑ Omer Reingold, Salil Vadhan et Avi Wigderson, « Entropy waves, the zig-zag graph product, and new constant-degree expanders », Annals of Mathematics, vol. 155, no 1, 2002, p. 157–187 [texte intégral, lien DOI, lien JSTOR] 
  24. ↑ Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4, 2008, p. 1–24 [texte intégral] 
  25. ↑ Sanjeev Arora, « Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems », Journal of the ACM, vol. 45, no 5, 1998, p. 753–782 [lien DOI] 
  26. ↑ Joseph S. B. Mitchell, « Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems », SIAM Journal on Computing, vol. 28, no 4, 1999, p. 1298–1309 (ISSN 1095-7111) [lien DOI] 
  27. ↑ Johan Håstad, « Some optimal inapproximability results », Journal of the ACM, vol. 48, 2001, p. 798–859 [texte intégral, lien DOI] 
  28. ↑ Elias Koutsoupias et Christos Papadimitriou, « Worst-case equilibria », Computer Science Review, vol. 3, no 2, 2009, p. 65–69 [lien DOI] 
  29. ↑ Tim Roughgarden et Éva Tardos, « How bad is selfish routing? », Journal of the ACM, vol. 49, no 2, 2002, p. 236–259 [lien DOI] 
  30. ↑ Noam Nisan et Amir Ronen, « Algorithmic Mechanism Design », Games and Economic Behavior, vol. 35, no 1-2, 2001, p. 166–196 [lien DOI] 

Notes [modifier]

Notes [modifier]

  1. ↑ Premiers paragraphes de la page du prix

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gödel Prize » (voir la liste des auteurs)

Article connexe [modifier]

Liens externes [modifier]

v · d · m
Lauréats du prix Gödel
1993 : László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran et Charles Rackoff • 1994 : Johan Håstad • 1995 : Neil Immerman, Róbert Szelepcsényi • 1996 : Mark Jerrum, Alistair Sinclair • 1997 : Joseph Halpern (en), Yoram Moses (en) • 1998 : Seinosuke Toda (en) • 1999 : Peter Shor • 2000 : Moshe Vardi, Pierre Wolper • 2001 : Sanjeev Arora, Uriel Feige (en), Shafi Goldwasser, Carsten Lund (en), László Lovász, Rajeev Motwani (en), Shmuel Safra (en), Madhu Sudan, Mario Szegedy • 2002 : Géraud Sénizergues • 2003 : Yoav Freund, Robert Schapire • 2004 : Maurice Herlihy (en), Michael Saks (en), Nir Shavit (en), Fotios Zaharoglou • 2005 : Noga Alon (en), Yossi Matias, Mario Szegedy • 2006 : Manindra Agrawal, Neeraj Kayal (en), Nitin Saxena (en) • 2007 : Alexander Razborov, Steven Rudich (en) • 2008 : Shanghua Teng (en), Daniel Spielman • 2009 : Omer Reingold (en), Salil Vadhan (en), Avi Wigderson • 2010 : Sanjeev Arora, Joseph Mitchell (en) • 2011 : Johan Håstad • 2012 : Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden et Éva Tardos
Ce document provient de « http://fr.wikipedia.org/w/index.php?title=Prix_Gödel&oldid=92904118 ».