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 . 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édentesPremiers paragraphes de la page du prix. 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=NPSur 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..
Lauréats +Liste des lauréatsAnnéeNom(s) Contribution(s)1993László Babai () et Shlomo Moran (), Shafi Goldwasser (/), Silvio Micali (/) et Charles Rackoff ()Développement de la notion de système de preuve interactive1994Johan Håstad ()Bornes sur des problèmes de circuits booléens, et en particulier sur la fonction parité1995Neil Immerman () et Róbert Szelepcsényi ()Leur théorème reliant les classes NSPACE et co-NSPACE1996Mark Jerrum () et Alistair Sinclair ()Leurs travaux sur les chaînes de Markov et l'approximation du permanent1997Joseph Halpern () et Yoram Moses ()Le développement de la notion d'information dans le contexte des systèmes distribués1998Seinosuke Toda ()Son théorème reliant les classes de complexité PP et PH1999Peter Shor ()L'algorithme de Shor , qui permet de factoriser les nombres en temps polynomial sur un ordinateur quantique2000Moshe Vardi () et Pierre Wolper ()Leur travail sur la logique temporelle dans le cadre des automates finis2001Sanjeev Arora (), Uriel Feige (), Shafi Goldwasser (/), Carsten Lund (), László Lovász (/), Rajeev Motwani (), Shmuel Safra (), Madhu Sudan () et Mario Szegedy (/) Leur théorème PCP2002Géraud Sénizergues ()Avoir démontré la décidabilité de l'égalité de deux langages reconnus par des automates à piles déterministes2003Yoav Freund () et Robert Schapire ()L'algorithme AdaBoost en apprentissage automatique2004Maurice Herlihy (), Michael Saks (), Nir Shavit (), Fotios Zaharoglou ()L'application de notions de topologie au calcul distribué2005Noga Alon (), Yossi Matias () et Mario Szegedy ()Leurs contributions aux algorithmes de fouille de flots de données2006Manindra Agrawal (), Neeraj Kayal () et Nitin Saxena ()Le test de primalité AKS2007Alexandre Razborov () et Steven Rudich ()Leur article fondateur sur la preuve naturelle2008Shang-Hua Teng () et Daniel Spielman ()L'analyse lisse d'algorithme (smoothed analysis)2009Omer Reingold (), Salil Vadhan () et Avi Wigderson ()Le produit zig-zag de graphes2010Sanjeev Arora () et Joseph S. B. Mitchell ()Le schéma d'approximation polynomiale du problème du voyageur de commerce dans le cas euclidien2011Johan Håstad ()Des résultats de difficulté d'approximation, liés au théorème PCP2012Elias Koutsoupias (), Christos Papadimitriou (), Noam Nisan (), Amir Ronen (), Tim Roughgarden () et Éva Tardos ()La création de la théorie algorithmique des jeux2013Dan Boneh (), Matthew K. Franklin () et Antoine Joux ()L'introduction de la cryptographie à base de couplages2014Ronald Fagin (), Amnon Lotem () et Moni NaorAnnonce officielle du prix Godel 2014.Article à propos de l'article et du prix : . ()Les algorithmes d’agrégation optimaux2015Shang-Hua Teng () et Daniel Spielman ()Leurs travaux d'algèbre linéaire numérique, et l'application à l'algorithmique des graphes et à la théorie spectrale des graphes...2016Stephen D. Brookes () et Peter O'Hearn ()L'invention de la logique de séparation concurrente..2017. Cynthia Dwork (), Frank McSherry (), Kobbi Nissim () et Adam D. Smith ()L'invention de la confidentialité différentielle.2018Oded Regev ()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 () Pour une preuve fondamentalement différent du théorème PCP, plus simple, plus direct et plus efficace .2020 Robin A. Moser () et Gábor Tardos () Pour une version algorithmique du lemme local de Lovász
.2021 Andrei Bulatov, Jin-Yi Cai (/), Xi Chen (), Martin Dyer () et David Richerby Classification de la complexité de comptage des problèmes de satisfaction de contraintes .2022 Zvika Brakerski (), Vinod Vaikuntanathan () et Craig Gentry () Construction de schémas de chiffrement totalement homomorphes efficaces 2023Samuel Fiorini (), Serge Massar (), Sebastian Pokutta (), Hans Raj Tiwary, Ronald de Wolf () et Thomas Rothvoss ()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.2024Ryan Williamspour ses travaux sur les bornes inférieures des circuits et son paradigmes sur les « algorithmes sur les bornes inférieures »2025.Eshan Chattopadhyay et David Zuckermanpour leurs travaux sur les fonctions résilientes“Explicit two-source extractors and resilient functions”, STOC 2016
Articles distingués
Notes Notes
Voir aussi Articles connexes Liste de prix en informatique Prix Knuth
Liens externes Prix Gödel sur l'EATCS Prix Gödel sur SIGACT
Gödel Catégorie:Événement en informatique Catégorie:Informatique théorique Catégorie:Kurt Gödel