# Prix Gödel

Le prix Gödel est une distinction créée en 1992 par l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'Association for Computing Machinery (ACM) pour honorer des travaux remarquables d'informatique théorique. Il est nommé en l'honneur du logicien Kurt Gödel.

## Description

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. Le prix Gödel est considéré comme l'un des deux plus grands prix internationaux en informatique, avec le prix Turing.
Le prix est nommé en l'honneur de Kurt Gödel, pour ses travaux en logique mathématique, et son intuition du problème P=NP.

## Lauréats

Liste des lauréats :
| Année | Nom(s) | Contribution(s) |
| 1993 | László Babai ( Hongrie) et Shlomo Moran ( Israël), Shafi Goldwasser ( Israël/ États-Unis), Silvio Micali ( Italie/ États-Unis) et Charles Rackoff ( États-Unis) | Développement de la notion de système de preuve interactive |
| 1994 | Johan Håstad ( Suède) | Bornes sur des problèmes de circuits booléens, et en particulier sur la fonction parité |
| 1995 | Neil Immerman ( États-Unis) et Róbert Szelepcsényi ( Slovaquie) | Leur théorème reliant les classes NSPACE et co-NSPACE |
| 1996 | Mark Jerrum ( Royaume-Uni) et Alistair Sinclair ( Royaume-Uni) | Leurs travaux sur les chaînes de Markov et l'approximation du permanent |
| 1997 | Joseph Halpern ( États-Unis) et Yoram Moses ( Israël) | Le développement de la notion d'information dans le contexte des systèmes distribués |
| 1998 | Seinosuke Toda ( Japon) | Son théorème reliant les classes de complexité PP et PH |
| 1999 | Peter Shor ( États-Unis) | L'algorithme de Shor, qui permet de factoriser les nombres en temps polynomial sur un ordinateur quantique |
| 2000 | Moshe Vardi ( Israël) et Pierre Wolper ( Belgique) | Leur travail sur la logique temporelle dans le cadre des automates finis |
| 2001 | Sanjeev Arora ( États-Unis), Uriel Feige ( Israël), Shafi Goldwasser ( Israël/ États-Unis), Carsten Lund ( Danemark), László Lovász ( Hongrie/ États-Unis), Rajeev Motwani ( Inde), Shmuel Safra ( Israël), Madhu Sudan ( États-Unis) et Mario Szegedy ( Hongrie/ États-Unis) | Leur théorème PCP$^,$$^,$ |
| 2002 | Géraud Sénizergues ( France) | Avoir démontré la décidabilité de l'égalité de deux langages reconnus par des automates à piles déterministes |
| 2003 | Yoav Freund ( Israël) et Robert Schapire ( États-Unis) | L'algorithme AdaBoost en apprentissage automatique |
| 2004 | Maurice Herlihy ( États-Unis), Michael Saks ( États-Unis), Nir Shavit ( Israël), Fotios Zaharoglou ( Grèce) | L'application de notions de topologie au calcul distribué$^,$ |
| 2005 | Noga Alon ( Israël), Yossi Matias ( Israël) et Mario Szegedy ( Hongrie) | Leurs contributions aux algorithmes de fouille de flots de données |
| 2006 | Manindra Agrawal ( Inde), Neeraj Kayal ( Inde) et Nitin Saxena ( Inde) | Le test de primalité AKS |
| 2007 | Alexandre Razborov ( Russie) et Steven Rudich ( États-Unis) | Leur article fondateur sur la preuve naturelle |
| 2008 | Shang-Hua Teng ( Chine) et Daniel Spielman ( États-Unis) | L'analyse lisse d'algorithme (smoothed analysis) |
| 2009 | Omer Reingold ( Israël), Salil Vadhan ( États-Unis) et Avi Wigderson ( Israël) | Le produit zig-zag de graphes$^,$ |
| 2010 | Sanjeev Arora ( États-Unis) et Joseph S. B. Mitchell ( États-Unis) | Le schéma d'approximation polynomiale du problème du voyageur de commerce$^,$ dans le cas euclidien |
| 2011 | Johan Håstad ( Suède) | Des résultats de difficulté d'approximation, liés au théorème PCP |
| 2012 | Elias Koutsoupias ( Grèce), Christos Papadimitriou ( Grèce), Noam Nisan ( Israël), Amir Ronen ( Israël), Tim Roughgarden ( États-Unis) et Éva Tardos ( Hongrie) | La création de la théorie algorithmique des jeux$^,$$^,$ |
| 2013 | Dan Boneh ( Israël), Matthew K. Franklin ( États-Unis) et Antoine Joux ( France) | L'introduction de la cryptographie à base de couplages$^,$ |
| 2014 | Ronald Fagin ( États-Unis), Amnon Lotem ( Israël) et Moni Naor$^,$ ( Israël) | Les algorithmes d’agrégation optimaux |
| 2015 | Shang-Hua Teng ( Chine) et Daniel Spielman ( États-Unis) | Leurs travaux d'algèbre linéaire numérique, et l'application à l'algorithmique des graphes et à la théorie spectrale des graphes$^,$$^,$ |
| 2016 | Stephen D. Brookes ( Royaume-Uni) et Peter O'Hearn ( Canada) | L'invention de la logique de séparation concurrente$^,$ |
| 2017 | Cynthia Dwork ( États-Unis), Frank McSherry ( États-Unis), Kobbi Nissim ( Israël) et Adam D. Smith ( États-Unis) | L'invention de la confidentialité différentielle |
| 2018 | Oded Regev ( Israël) | L'introduction du problème de l'apprentissage avec erreurs, l'étude de sa complexité en moyenne par réduction aux problèmes de réseaux euclidiens, et son impact sur la cryptographie post-quantique |
| 2019 | Irit Dinur ( Israël) | Pour une preuve fondamentalement différent du théorème PCP, plus simple, plus direct et plus efficace. |
| 2020 | Robin A. Moser ( Suisse) et Gábor Tardos ( Hongrie) | Pour une version algorithmique du lemme local de Lovász. |
| 2021 | Andrei Bulatov, Jin-Yi Cai ( Chine/ États-Unis), Xi Chen ( États-Unis), Martin Dyer ( Royaume-Uni) et David Richerby | Classification de la complexité de comptage des problèmes de satisfaction de contraintes$^,$$^,$. |
| 2022 | Zvika Brakerski ( Israël), Vinod Vaikuntanathan ( Inde) et Craig Gentry ( États-Unis) | Construction de schémas de chiffrement totalement homomorphes efficaces$^,$ |
| 2023 | Samuel Fiorini ( Belgique), Serge Massar ( Belgique), Sebastian Pokutta ( Allemagne), Hans Raj Tiwary, Ronald de Wolf ( Pays-Bas) et Thomas Rothvoss ( Suisse) | Pour avoir montré que toute formulation étendue du polytope pour le problème du voyageur de commerce et pour le problème de couplage parfait a une taille exponentielle$^,$. |
| 2024 | Ryan Williams | pour ses travaux sur les bornes inférieures des circuits et son paradigmes sur les « algorithmes sur les bornes inférieures » |

## Articles distingués

* ↑ 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, n$^o$ 2,‎ 1988, p. 254–276 (DOI 10.1016/0022-0000(88)90028-1, lire en ligne)
* ↑ S. Goldwasser, S. Micali et C. Rackoff, « The knowledge complexity of interactive proof systems », SIAM Journal on Computing, vol. 18, n$^o$ 1,‎ 1989, p. 186–208 (DOI 10.1137/0218012, lire en ligne)
* ↑ 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 » (n$^o$ 5), 1989 (ISBN 0-89232-896-7, lire en ligne [archive du 22 février 2012]), « Almost Optimal Lower Bounds for Small Depth Circuits », p. 6–20
* ↑ Neil Immerman, « Nondeterministic space is closed under complementation », SIAM Journal on Computing, vol. 17, n$^o$ 5,‎ 1988, p. 935–938 (ISSN 1095-7111, DOI 10.1137/0217058, lire en ligne)
* ↑ R. Szelepcsényi, « The method of forced enumeration for nondeterministic automata », Acta Informatica, vol. 26, n$^o$ 3,‎ 1988, p. 279–284 (DOI 10.1007/BF00299636)
* ↑ Mark Jerrum et Alistair Sinclair, « Approximating the permanent », SIAM Journal on Computing, vol. 18, n$^o$ 6,‎ 1989, p. 1149–1178 (ISSN 1095-7111, DOI 10.1137/0218077)
* ↑ Alistair Sinclair et Mark Jerrum, « Approximate counting, uniform generation and rapidly mixing Markov chains », Information and Computation, vol. 82, n$^o$ 1,‎ 1989, p. 93–133 (DOI 10.1016/0890-5401(89)90067-9)
* ↑ Joseph Halpern et Yoram Moses, « Knowledge and common knowledge in a distributed environment », Journal of the ACM, vol. 37, n$^o$ 3,‎ 1990, p. 549–587 (DOI 10.1145/79147.79161)
* ↑ Seinosuke Toda, « PP is as hard as the polynomial-time hierarchy », SIAM Journal on Computing, vol. 20, n$^o$ 5,‎ 1991, p. 865–877 (DOI 10.1137/0220053, lire en ligne)
* ↑ Peter W. Shor, « Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer », SIAM Journal on Computing, vol. 26, n$^o$ 5,‎ 1997, p. 1484–1509 (DOI 10.1137/S0097539795293172, lire en ligne)
* ↑ Moshe Y. Vardi et Pierre Wolper, « Reasoning about infinite computations », Information and Computation, vol. 115, n$^o$ 1,‎ 1994, p. 1–37 (DOI 10.1006/inco.1994.1092)
* ↑ 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, n$^o$ 2,‎ 1996, p. 268–292 (DOI 10.1145/226643.226652, lire en ligne)
* ↑ Sanjeev Arora et Shmuel Safra, « Probabilistic checking of proofs: a new characterization of NP », Journal of the ACM, vol. 45, n$^o$ 1,‎ 1998, p. 70–122 (DOI 10.1145/273865.273901, lire en ligne [archive du 10 juin 2011])
* ↑ 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, n$^o$ 3,‎ 1998, p. 501–555 (DOI 10.1145/278298.278306, lire en ligne [archive du 10 juin 2011])
* ↑ Géraud Sénizergues, « L(A) = L(B)? decidability results from complete formal systems », Theor. Comput. Sci., vol. 251, n$^o$ 1,‎ 2001, p. 1–166 (DOI 10.1016/S0304-3975(00)00285-1)
* ↑ 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, n$^o$ 1,‎ 1997, p. 119–139 (DOI 10.1006/jcss.1997.1504, lire en ligne)
* ↑ Maurice Herlihy et Nir Shavit, « The topological structure of asynchronous computation », Journal of the ACM, vol. 46, n$^o$ 6,‎ 1999, p. 858–923 (DOI 10.1145/331524.331529, lire en ligne)
* ↑ Michael Saks et Fotios Zaharoglou, « Wait-free k-set agreement is impossible: The topology of public knowledge », SIAM Journal on Computing, vol. 29, n$^o$ 5,‎ 2000, p. 1449–1483 (DOI 10.1137/S0097539796307698)
* ↑ Noga Alon, Yossi Matias et Mario Szegedy, « The space complexity of approximating the frequency moments », Journal of Computer and System Sciences, vol. 58, n$^o$ 1,‎ 1999, p. 137–147 (DOI 10.1006/jcss.1997.1545, lire en ligne)
* ↑ Manindra Agrawal, Neeraj Kayal et Nitin Saxena, « PRIMES is in P », Annals of Mathematics, vol. 160, n$^o$ 2,‎ 2004, p. 781–793 (DOI 10.4007/annals.2004.160.781, lire en ligne [archive du 7 juin 2011])
* ↑ Alexander A. Razborov et Steven Rudich, « Natural proofs », Journal of Computer and System Sciences, vol. 55, n$^o$ 1,‎ 1997, p. 24–35 (DOI 10.1006/jcss.1997.1494)
* ↑ 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, n$^o$ 3,‎ 2004, p. 385–463 (lire en ligne [archive du 6 décembre 2009])
* ↑ Omer Reingold, Salil Vadhan et Avi Wigderson, « Entropy waves, the zig-zag graph product, and new constant-degree expanders », Annals of Mathematics, vol. 155, n$^o$ 1,‎ 2002, p. 157–187 (DOI 10.2307/3062153, JSTOR 3062153, MR 1888797, lire en ligne [archive du 7 décembre 2009])
* ↑ Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, n$^o$ 4,‎ 2008, p. 1–24 (lire en ligne)
* ↑ Sanjeev Arora, « Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems », Journal of the ACM, vol. 45, n$^o$ 5,‎ 1998, p. 753–782 (DOI 10.1145/290179.290180)
* ↑ 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, n$^o$ 4,‎ 1999, p. 1298–1309 (ISSN 1095-7111, DOI 10.1137/S0097539796309764)
* ↑ 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)
* ↑ Elias Koutsoupias et Christos Papadimitriou, « Worst-case equilibria », Computer Science Review, vol. 3, n$^o$ 2,‎ 2009, p. 65–69 (DOI 10.1016/j.cosrev.2009.04.003)
* ↑ Tim Roughgarden et Éva Tardos, « How bad is selfish routing? », Journal of the ACM, vol. 49, n$^o$ 2,‎ 2002, p. 236–259 (DOI 10.1145/506147.506153)
* ↑ Noam Nisan et Amir Ronen, « Algorithmic Mechanism Design », Games and Economic Behavior, vol. 35, n$^{os}$ 1-2,‎ 2001, p. 166–196 (DOI 10.1006/game.1999.0790)
* ↑ Dan Boneh et Matthew Franklin, « Identity-based encryption from the Weil pairing », SIAM Journal on Computing, vol. 32, n$^o$ 3,‎ 2003, p. 586–615 (DOI 10.1137/S0097539701398521, MR 2001745)
* ↑ Antoine Joux, « A one round protocol for tripartite Diffie-Hellman », Journal of Cryptology, vol. 17, n$^o$ 4,‎ 2004, p. 263–276 (DOI 10.1007/s00145-004-0312-y, MR 2090557)
* ↑ Ronald Fagin, Amnon Lotem et Moni Naor, « Optimal aggregation algorithms for middleware », Journal of Computer and System Sciences, vol. 66, n$^o$ 4,‎ 2003, p. 614-656 (DOI 10.1016/S0022-0000(03)00026-6)
* ↑ Daniel A. Spielman et Shang-Hua Teng, « Spectral Sparsification of Graphs », SIAM Journal on Computing, vol. 40, n$^o$ 4,‎ 2011, p. 981-1025 (ISSN 0097-5397, DOI 10.1137/08074489X).
* ↑ Daniel A. Spielman et Shang-Hua Teng, « A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning », SIAM Journal on Computing, vol. 42, n$^o$ 1,‎ 2013, p. 1-26 (ISSN 0097-5397, DOI 10.1137/080744888).
* ↑ Daniel A. Spielman et Shang-Hua Teng, « Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems », SIAM Journal on Matrix Analysis and Applications, vol. 35, n$^o$ 3,‎ 2014, p. 835-885 (ISSN 0895-4798, DOI 10.1137/090771430).
* ↑ Peter W. O’Hearn, « Resources, Concurrency, and Local Reasoning », Theoretical Computer Science, vol. 375, n$^{os}$ 1-3,‎ 2007, p. 271-307.
* ↑ Stephen Brookes, « A Semantics for Concurrent Separation Logic », Theoretical Computer Science, vol. 375, n$^{os}$ 1-3,‎ 2007, p. 227-270.
* ↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith, « Calibrating Noise to Sensitivity », Private Data Analysis Journal of Privacy and Confidentiality, vol. 7, n$^o$ 3,‎ 2016.
* ↑ (en) Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », Journal of the ACM, vol. 56, n$^o$ 6,‎ 2009, p. 34:1-34:40 (DOI 10.1145/1568318.1568324).
* ↑ (en) Irit Dinur, « The PCP theorem by gap amplification », Journal of the ACM, vol. 54, n$^o$ 3,‎ 2007, p. 12
* ↑ (en) Robin A. Moser et Gábor Tardos, « A constructive proof of the general Lovász Local Lemma », Journal of the ACM, vol. 57, n$^o$ 2,‎ 2010, p. 11:1-11:15
* ↑ Andrei A. Bulatov, « The complexity of the counting constraint satisfaction problem », Journal of the ACM, Association for Computing Machinery (ACM), vol. 60, n$^o$ 5,‎ 2013, p. 1–41 (ISSN 0004-5411, DOI 10.1145/2528400)
* ↑ Martin Dyer et David Richerby, « An Effective Dichotomy for the Counting Constraint Satisfaction Problem », Society for Industrial & Applied Mathematics (SIAM), vol. 42, n$^o$ 3,‎ 2013, p. 1245–1274 (ISSN 0097-5397, DOI 10.1137/100811258)
* ↑ Jin-Yi Cai et Xi Chen, « Complexity of Counting CSP with Complex Weights », Association for Computing Machinery (ACM), vol. 64, n$^o$ 3,‎ 22 juin 2017, p. 1–39 (ISSN 0004-5411, DOI 10.1145/2822891)
* ↑ Zvika Brakerski et Vinod Vaikuntanathan, « Efficient Fully Homomorphic Encryption from (Standard) LWE », SIAM Journal on Computing, vol. 43, n$^o$ 2,‎ 2014, p. 831-871
* ↑ Zvika Brakerski, Craig Gentry et Vinod Vaikuntanathan, « (Leveled) fully homomorphic encryption without bootstrapping », ACM Transactions on Computation Theory, vol. 6, n$^o$ 3,‎ 2014, p. 13:1-13:36
* ↑ (en) Samuel Fiorini, Serge Massar, Sebastian Pokutta et Hans Raj Tiwary, « Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds », Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, ACM,‎ 19 mai 2012, p. 95–106 (ISBN 978-1-4503-1245-5, DOI 10.1145/2213977.2213988, lire en ligne, consulté le 2 juin 2023)
* ↑ (en) Thomas Rothvoss, « The matching polytope has exponential extension complexity », Proceedings of the 46th Symposium on Theory of Computing Conference, STOC 2014, ACM,‎ 31 mai 2014, p. 263–272 (ISBN 978-1-4503-2710-7, DOI 10.1145/2591796.2591834, lire en ligne, consulté le 2 juin 2023)
* ↑ Ryan Williams, 2011 IEEE 26th Annual Conference on Computational Complexity, IEEE, juin 2011, 115–125 p. (ISBN 978-1-4577-0179-5, DOI 10.1109/ccc.2011.36), « Non-uniform ACC Circuit Lower Bounds »