El Premi Gödel és un premi que es lliura a autors d'articles relacionats amb la teoria de la computació. El nom del premi es deu al matemàtic Kurt Gödel, i és atorgat per l'Associació Europea per a la Informàtica Teòrica (EATCS) i el Grup d'Interès Especial d'Algorismes i Teoria de la Computació de l'Association for Computing Machinery (ACM).
El Premi Gödel es lliura anualment des de 1993, ja sigui en lSTOC (ACM Symposium on Theory of Computing), una de les principals conferències dels Estats Units en l'àrea d'informàtica teòrica, o bé en lICALP (International Colloquium on Automata, Languages, and Programming), una de les principals conferències europees a la mateixa àrea. A part de la distinció, inclou un bo de 5000 dòlars. Com a requisit per rebre el premi, l'article guanyador ha d'haver estat publicat en una revista científica un màxim de 14 anys enrere (anteriorment n'eren només 7 anys).
Guanyadors 1993 - László Babai i Shlomo Moran, Shafi Goldwasser, Silvio Micali i Charles Rackoff, pel desenvolupament de sistemes de demostració interactius.
1994 - Johan Håstad, per trobar una cota inferior exponencial en funció de la mida de profunditat-constant d'un circuit booleà per a la funció paritat.
1995 - Neil Immerman i Róbert Szelepcsényi, pel Teorema d'Immerman-Szelepcsényi, de vinculació de classes NSPACE i co-NSPACE.
1996 - Mark Jerrum i Alistair Sinclair pel seu treball en les cadenes de Markov i l'aproximació la permanent.
1997 - Joseph Halpern i Yoram Moses, pel desenvolupament del concepte de la informació en el context de sistemes distribuïts. 1998 - Seinosuke Toda pel seu teorema entre classes de complexitat PP i PH.
1999 - Peter Shor, per l'Algoritme de Shor, per factoritzar nombres en temps polinòmic en un computador quàntic.
2000 - Moshe Y. Vardi i Pierre Wolper, pel seu treball en la lògica temporal com a part dels autòmats finits.
2001 - Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan i Mario Szegedypour leur théorème PCP .
2002 - Géraud Sénizergues, per demostrar que l'equivalència d'autòmats de pila deterministes és decidible. 2003 - Yoav Freund i Robert Schapire, per l'algoritme AdaBoost en l'aprenentatge automàtic.
2004 - Maurice Herlihy, Mike Saks, Nir Shavit i Fotios Zaharoglou, per aplicar topologia a la teoria de computació distribuïda.
2005 - Noga Alon, Yossi Matias i Mario Szegedy per les seves contribucions en els algoritmes de mineria de fluxos de dades.
2006 - Manindra Agrawal, Neeraj Kayal, Nitin Saxena, pel Test de primalitat AKS.
2007 - Alexander Razborov i Steven Rudich, per les demostracions naturals.
2008 - Shanghua Teng i Daniel Spielman, per l'anàlisi Smoothed de logaritmes.
2009 - Omer Reingold, Avi Wigderson i Salil Vadhan, per l'anàlisi d'SL (complexitat).
2010 - Sanjeev Arora i Joseph S. B. Mitchell per l'esquema d'aproximació polinòmica del problema del viatjant de comerç en el cas euclidiana.
2011 - Johan Håstad, per resultats de dificultat d'aproximació, relacionat amb el teorema PCP.
2012 - Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden i Éva Tardos, per a la creació de la teoria algorísmica dels jocs (a mig camí entre l'algorísmica i la teoria dels jocs).
2013 - Dan Boneh, Matthew K. Franklin, i Antoine JouxACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security , Association for Computing Machinery, May 29, 2013. per a la introducció i l'ús del concepte dacoblament (en anglès) a criptografia.
Articles distingits
Referències
Vegeu també Premi Knuth
Enllaços externs
Prix Gödel en l'EATCS Prix Gödel en SIGACT
Categoria:Esdeveniments del món de la informàtica Categoria:Informàtica teòrica Gödel