Prix Gödel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Prix Gödel
Date de création 1992

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.

Description[modifier | modifier le code]

Kurt Gödel en 1925

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]. Le prix Gödel est considéré comme l'un des deux plus grands prix internationaux en informatique, avec le prix Turing[2].

Le prix est nommé en l'honneur de Kurt Gödel, pour ses travaux en logique mathématiques, et son intuition du problème P=NP[3].

Lauréats[modifier | modifier le code]

Articles distingués[modifier | modifier le code]

  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 (DOI 10.1016/0022-0000(88)90028-1, lire en ligne)
  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 (DOI 10.1137/0218012, lire en ligne)
  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), « Almost Optimal Lower Bounds for Small Depth Circuits », 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, DOI 10.1137/0217058, lire en ligne)
  5. R. Szelepcsényi, « The method of forced enumeration for nondeterministic automata », Acta Informatica, vol. 26, no 3,‎ 1988, p. 279–284 (DOI 10.1007/BF00299636)
  6. Mark Jerrum et Alistair Sinclair, « Approximating the permanent », SIAM Journal on Computing, vol. 18, no 6,‎ 1989, p. 1149–1178 (ISSN 1095-7111, DOI 10.1137/0218077)
  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 (DOI 10.1016/0890-5401(89)90067-9)
  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 (DOI 10.1145/79147.79161)
  9. Seinosuke Toda, « PP is as hard as the polynomial-time hierarchy », SIAM Journal on Computing, vol. 20, no 5,‎ 1991, p. 865–877 (DOI 10.1137/0220053, lire en ligne)
  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 (DOI 10.1137/S0097539795293172, lire en ligne)
  11. Moshe Y. Vardi et Pierre Wolper, « Reasoning about infinite computations », Information and Computation, vol. 115, no 1,‎ 1994, p. 1–37 (DOI 10.1006/inco.1994.1092, lire en ligne)
  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 (DOI 10.1145/226643.226652, lire en ligne)
  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 (DOI 10.1145/273865.273901, lire en ligne)
  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 (DOI 10.1145/278298.278306, lire en ligne)
  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 (DOI 10.1016/S0304-3975(00)00285-1)
  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 (DOI 10.1006/jcss.1997.1504, lire en ligne)
  17. Maurice Herlihy et Nir Shavit, « The topological structure of asynchronous computation », Journal of the ACM, vol. 46, no 6,‎ 1999, p. 858–923 (DOI 10.1145/331524.331529, lire en ligne)
  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 (DOI 10.1137/S0097539796307698)
  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 (DOI 10.1006/jcss.1997.1545, lire en ligne)
  20. M. Agrawal, N. Kayal et N. Saxena, « PRIMES is in P », Annals of Mathematics, vol. 160, no 2,‎ 2004, p. 781–793 (DOI 10.4007/annals.2004.160.781, lire en ligne)
  21. Alexander A. Razborov et Steven Rudich, « Natural proofs », Journal of Computer and System Sciences, vol. 55, no 1,‎ 1997, p. 24–35 (DOI 10.1006/jcss.1997.1494)
  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 (lire en ligne)
  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 (DOI 10.2307/3062153, JSTOR 3062153, lire en ligne)
  24. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ 2008, p. 1–24 (lire en ligne)
  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 (DOI 10.1145/290179.290180)
  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, DOI 10.1137/S0097539796309764)
  27. Johan Håstad, « Some optimal inapproximability results », Journal of the ACM, vol. 48,‎ 2001, p. 798–859 (DOI 10.1145/502090.502098, lire en ligne)
  28. Elias Koutsoupias et Christos Papadimitriou, « Worst-case equilibria », Computer Science Review, vol. 3, no 2,‎ 2009, p. 65–69 (DOI 10.1016/j.cosrev.2009.04.003)
  29. Tim Roughgarden et Éva Tardos, « How bad is selfish routing? », Journal of the ACM, vol. 49, no 2,‎ 2002, p. 236–259 (DOI 10.1145/506147.506153)
  30. Noam Nisan et Amir Ronen, « Algorithmic Mechanism Design », Games and Economic Behavior, vol. 35, no 1-2,‎ 2001, p. 166–196 (DOI 10.1006/game.1999.0790)
  31. Dan Boneh et Matthew Franklin, « Identity-based encryption from the Weil pairing », SIAM Journal on Computing, vol. 32, no 3,‎ 2003, p. 586–615 (DOI 10.1137/S0097539701398521)
  32. Antoine Joux, « A one round protocol for tripartite Diffie-Hellman », Journal of Cryptology, vol. 17, no 4,‎ 2004, p. 263–276 (DOI 10.1007/s00145-004-0312-y)
  33. Ronald Fagin, Amnon Lotem et Moni Naor, « Optimal aggregation algorithms for middleware », Journal of Computer and System Sciences, vol. 66, no 4,‎ 2003, p. 614-656 (DOI 10.1016/S0022-0000(03)00026-6)

Notes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Premiers paragraphes de la page du prix
  2. Jacques Stern, « Antoine Joux, Prix Gödel 2013 », 1024 - Bulletin de la société informatique de France, no 1,‎ septembre 2013, p. 107-110 (lire en ligne)
  3. Sur le site de l'EATCS : Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann's death, in what has become the famous "P versus NP" question.
  4. Annonce officielle du prix Godel 2014.

(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)

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Liens externes[modifier | modifier le code]