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| 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 |
Altri progetti
modifica
Wikimedia Commons contiene immagini o altri file su premio Gödel
Collegamenti esterni
modifica- Il sito del premio con l’elenco dei vincitori, su sigact.org. URL consultato il 2 giugno 2011 (archiviato dall'url originale il 7 ottobre 2016).
