Apri il menu principale

Il premio Gödel è un premio per lavori originali e straordinari in informatica teorica. Prende il suo nome dal matematico Kurt Gödel ed è bandito annualmente, dal 1993, congiuntamente dall'EATCS e dall'ACM. Il premio comprende una somma di $ 5.000. Un lavoro scientifico, per essere preso in considerazione ai fini del premio, deve essere stato pubblicato nei 14 anni precedenti su una delle principali riviste matematiche internazionali accreditate.

Elenco dei vincitoriModifica

Anno Vincitore (i) Motivazione
1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran e Charles Rackoff per lo sviluppo di un sistema crittografico interattivo.
1994 Johan Håstad per una dimostrazione sulla dimensione dei circuiti booleani.
1995 Neil Immerman e Róbert Szelepcsényi per il Teorema di Immerman-Szelepcsényi, riguardante la complessità dello spazio non deterministica.
1996 Mark Jerrum e Alistair Sinclair per un lavoro sulle Proprietà di Markov e sull'approssimazione di un permanente di una matrice.
1997 Joseph Halpern e Yoram Moses per aver definite una formale conoscenza negli ambienti distribuiti.
1998 Seinosuke Toda per il Teorema di Toda che dimostrava la connessione tra soluzioni di conteggio e alternarsi di quantificatori.
1999 Peter Shor per l'Algoritmo di fattorizzazione di Shor che si utilizza per fattorizzare numeri usando un vecchio trucco della Teoria dei numeri.
2000 Moshe Y. Vardi e Pierre Wolper per un lavoro sulle logiche temporali e gli automi a stati finiti.
2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, e Mario Szegedy per il Teorema PCP e le sue applicazioni alla difficoltà dell'approssimazione.
2002 Géraud Sénizergues per aver dimostrato che la ricerca deterministica automatica è discreta.
2003 Yoav Freund e Robert Schapire per l'algoritmo “AdaBoost”.
2004 Maurice Herlihy, Mike Saks, Nir Shavit e Fotios Zaharoglou per l'applicazione della topografia alla teoria della computazione distribuita.
2005 Noga Alon, Yossi Matias e Mario Szegedy per il loro fondamentale contributo alla stesura degli algoritmi.
2006 Manindra Agrawal, Neeraj Kayal e Nitin Saxena per l'Algoritmo AKS, un test di primalità in tempo polinomiale.
2007 Alexander Razborov e Steven Rudich per la prova naturale.
2008 Shanghua Teng e Daniel Spielman per un'analisi degli algoritmi.
2009 Omer Reingold, Salil Vadhan e Avi Wigderson per miglioramenti nella costruzione ed applicazione di efficienti expander grafici che aiutano a risolvere complessi problemi di calcolo
2010 Sanjeev Arora e Joseph S. B. Mitchell
2011 Johan Håstad
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden e Éva Tardos
2013 Dan Boneh, Matthew K. Franklin, Antoine Joux

Collegamenti esterniModifica