Prix Gödel - Définition

Introduction

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), l'Association for Computing Machinery (ACM) et le groupe de l'ACM sur l'algorithmique et la théorie du calcul (SIGACT) 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. Pour être éligible, un article du récipiendaire doit avoir été publié dans un journal avec comité de lecture dans les 14 années précédentes.

Lauréats

• 1993 - László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran et Charles Rackoff pour le développement de la notion de Système de preuve interactive
• 1994 - Johan Håstad
• 1995 - Neil Immerman et Róbert Szelepcsényi
• 1996 - Mark Jerrum et Alistair Sinclair
• 1997 - Joseph Halpern et Yoram Moses
• 1998 - Seinosuke Toda
• 1999 - Peter Shor pour l'algorithme de Shor, qui permet de factoriser les nombres en temps polynomial sur un ordinateur quantique
• 2000 - Moshe Vardi et Pierre Wolper
• 2001 - Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan et Mario Szegedy
• 2002 - Géraud Sénizergues, pour avoir démontré la décidabilité de l'égalité de deux langages reconnus par des automates à piles.
• 2003 - Yoav Freund et Robert Schapire
• 2004 - Maurice Herlihy, Mike Saks, Nir Shavit et Fotios Zaharoglou
• 2005 - Noga Alon, Yossi Matias et Mario Szegedy
• 2006 - Manindra Agrawal, Neeraj Kayal, Nitin Saxena pour le test de primalité AKS
• 2007 - Alexander Razborov, Steven Rudich
• 2008 - Shanghua Teng et Daniel Spielman pour l'analyse lisse des algorithmes (smoothed analysis)
• 2009 - Omer Reingold, Salil Vadhan et Avi Wigderson pour le produit zig-zag de graphes
• 2010 - Sanjeev Arora et Joseph S. B. Mitchell pour le schéma d'approximation polynomiale du problème du voyageur de commerce dans le cas euclidien.