Premio Gödel

Da Wikipedia, l'enciclopedia libera.

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 vincitori[modifica | modifica sorgente]

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 sul controllo dei modelli.
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 esterni[modifica | modifica sorgente]