Premio Gödel

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 5000 $. 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 vincitori

[modifica | modifica wikitesto]

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 topologia 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