Année |
Nom(s) |
Contribution(s) |
1993 |
László Babai ( Hongrie) et Shlomo Moran[A 1] ( Israël), Shafi Goldwasser ( Israël/ États-Unis), Silvio Micali ( Italie/ États-Unis) et Charles Rackoff[A 2] ( États-Unis) |
Développement de la notion de système de preuve interactive |
1994 |
Johan Håstad[A 3] ( Suède) |
Bornes sur des problèmes de circuits booléens, et en particulier sur la fonction parité |
1995 |
Neil Immerman[A 4] ( États-Unis) et Róbert Szelepcsényi[A 5] ( Slovaquie) |
Leur théorème reliant les classes NSPACE et co-NSPACE |
1996 |
Mark Jerrum[A 6] ( Royaume-Uni) et Alistair Sinclair[A 7] ( Royaume-Uni) |
Leurs travaux sur les chaînes de Markov et l'approximation du permanent |
1997 |
Joseph Halpern ( États-Unis) et Yoram Moses[A 8] ( 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[A 9] reliant les classes de complexité PP et PH |
1999 |
Peter Shor ( États-Unis) |
L'algorithme de Shor [A 10], qui permet de factoriser les nombres en temps polynomial sur un ordinateur quantique |
2000 |
Moshe Vardi ( Israël) et Pierre Wolper ( Belgique) |
Leur travail[A 11] 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[A 12],[A 13],[A 14] |
2002 |
Géraud Sénizergues ( France) |
Avoir démontré la décidabilité[A 15] 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[A 16] |
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é[A 17],[A 18] |
2005 |
Noga Alon ( Israël), Yossi Matias ( Israël) et Mario Szegedy ( Hongrie) |
Leurs contributions[A 19] 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[A 20] |
2007 |
Alexandre Razborov ( Russie) et Steven Rudich ( États-Unis) |
Leur article fondateur sur la preuve naturelle[A 21] |
2008 |
Shang-Hua Teng ( Chine) et Daniel Spielman ( États-Unis) |
L'analyse lisse d'algorithme (smoothed analysis)[A 22] |
2009 |
Omer Reingold ( Israël), Salil Vadhan ( États-Unis) et Avi Wigderson ( Israël) |
Le produit zig-zag de graphes[A 23],[A 24] |
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[A 25],[A 26] dans le cas euclidien |
2011 |
Johan Håstad ( Suède) |
Des résultats de difficulté d'approximation, liés au théorème PCP[A 27] |
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[A 28],[A 29],[A 30] |
2013 |
Dan Boneh ( Israël), Matthew K. Franklin ( États-Unis) et Antoine Joux ( France) |
L'introduction de la cryptographie à base de couplages[A 31],[A 32] |
2014 |
Ronald Fagin ( États-Unis), Amnon Lotem ( Israël) et Moni Naor[4],[5] ( Israël) |
Les algorithmes d’agrégation optimaux[A 33] |
2015[6] |
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[A 34],[A 35],[A 36] |
2016[7] |
Stephen D. Brookes ( Royaume-Uni) et Peter O'Hearn ( Canada) |
L'invention de la logique de séparation concurrente[A 37],[A 38] |
2017[8] |
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[A 39] |
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[A 40] |
2019 |
Irit Dinur ( Israël) |
Pour une preuve fondamentalement différent du théorème PCP, plus simple, plus direct et plus efficace[A 41]. |
2020 |
Robin A. Moser ( Suisse) et Gábor Tardos ( Hongrie) |
Pour une version algorithmique du lemme local de Lovász[A 42]. |
2021[9] |
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[A 43],[A 44],[A 45]. |
2022[10] |
Zvika Brakerski ( Israël), Vinod Vaikuntanathan ( Inde) et Craig Gentry ( États-Unis) |
Construction de schémas de chiffrement totalement homomorphes efficaces[A 46],[A 47] |
2023[11] |
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[A 48],[A 49]. |