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 |
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su premio Gödel
Collegamenti esterni[modifica | modifica wikitesto]
- 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).
