A Gödel -díj a Kurt Gödel -díj számítástechnikai rendszerelméletben , amelyet az ACM SIGACT ( Speciális Érdeklődési Csoport az Algoritmusokkal és Számításelmélettel ) és az EATCS ( Európai Számítástechnikai Szövetség ) ad át évente a logika és az elméleti számítástechnika területén végzett kiemelkedő munkájáért .
A díjat 1993 óta ítélik oda, és 5000 dolláros pénzjutalom kíséri [1] . A díj odaítélésére vagy az amerikai STOC szimpóziumon ( Számítástechnikai Szimpózium ), vagy az ICALP európai konferencián ( International Colloquium on Automata, Languages and Programming ) kerül sor. A munkával szemben támasztott fő követelmény az első megjelenés dátuma - csak 14 évnél nem régebbi alkotásokkal lehet nevezni.
| Év | Név | Megjegyzések |
|---|---|---|
| 1993 | Babai László , Shafi Goldwasser , Silvio Micali , Shlomo Moran és Charles Rakoff | interaktív bizonyító rendszerek fejlesztéséhez [2] [3] . |
| 1994 | Johan Hostad | a paritásszámlálás exponenciális alsó korlátjának bizonyítására állandó mélységű Boole-sémák segítségével [4] [5] . |
| 1995 | Neil Immerman [ , Robert Shelepcheni | az Immermann-Shelepcheni tételhez ( számítási komplexitáselmélet ) [6] [7] . |
| 1996 | Mark Jerram , Alistair Sinclair | a Markov-láncokkal és a mátrixok állandójának közelítésével kapcsolatos kutatásaiért [8] [9] . |
| 1997 | Joseph Halpern , Yoram Moses | a "tudás" fogalmának formális meghatározásához elosztott környezetekben [10] [11] . |
| 1998 | Seinosuke Toda | Toda tételére , amely a PP és PH komplexitási osztályok közötti kapcsolatot mutatta meg [12] [13] . |
| 1999 | Peter Shore | a Shor -algoritmushoz számok polinomiális időn belüli faktorálására kvantumszámítógépen [14] [15] . |
| 2000 | Moshe Vardy , Pierre Wolper | véges automatákkal végzett modellellenőrzéssel kapcsolatos kutatásaihoz [16] [17] . |
| 2001 | Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani Shmuel Safra , Sudan , Mario Szegedi | a PCP-tételhez és annak alkalmazásához [18] [19] . |
| 2002 | Jéro Senizerg | determinisztikus lenyomó automaták ekvivalenciája megoldhatóságának bizonyítására [20] [21] . |
| 2003 | Yoav Freund és Robert Shapire | az AdaBoost algoritmushoz [22] [23] . |
| 2004 | Maurice Herlihy , Michael Sachs Nir Shavit és Fotios Zaharoglu | a topológia alkalmazásához az elosztott számítástechnika elméletére [24] [25] . |
| 2005 | Noga Alon , Yossi Matias , Mario Szegedi | alapos kutatásokhoz a streaming algoritmusok területén [26] [27] . |
| 2006 | Manindra Agrawal , Niraj Kayal , Nitin Saxena | az Agrawal-Kayala-Szászország teszthez [28] [29] . |
| 2007 | Alexander Razborov , Steven Rudich | a " természetes bizonyításokra " [30] [31] . |
| 2008 | Teng Shanhua , Daniel Speelman | algoritmusok " sima elemzéséhez " [32] . |
| 2009 | Omer Reingold , Salil Wadhan , Avi Wigderson | gráfok cikk-cakk szorzatára és egy determinisztikus, logaritmikus algoritmus megtalálására a memóriában az irányítatlan st-kapcsolódási[33] . |
| 2010 | Sanjiv Arora , Joseph Mitchell | az euklideszi utazó értékesítő probléma időpolinomiális közelítési sémájának (PTAS) felfedezéséhez [34] . |
| 2011 | Johan Hostad | a nem közelíthetőség bizonyítására különféle kombinatorikai problémákra [35] . |
| 2012 | Elias Koutsoupias , Christos Papadimitriou , Tim Roukhgarden , Eva Tardos , Noam Nisan , Amir Ronen | Hozzájárulásáért annak megértéséhez, hogy a felhasználók és a szolgáltatók önző magatartása hogyan hat az internet és más összetett számítástechnikai rendszerek viselkedésére [36] . |
| 2013 | Antoine Joux , Dan Bonet , Matthew C. Franklin | kriptográfiával kapcsolatos munkájáért [37] [38] . |
| 2014 | Ronald Fagin , Amnon Lotem , Moni Naor | a Middleware optimális aggregációs algoritmusaihoz [39] . |
| 2015 | Daniel Spielman , Teng Shanhua | lineáris egyenletrendszerek gyors megoldásáról szóló cikksorozathoz [40] [41] . |
| 2016 | Stephen Brooks , Peter O'Hearn | párhuzamos particionálási logika kifejlesztéséhez [42] . |
| 2017 | Cynthia Dwork , Frank McSherry , Kobe Nissim , Adam D. Smith | Differenciális adatvédelem [43] . |
| 2018 | Oded Regev | Tanulás hibákkal [44] . |
| 2019 | Irit Dinur [45] | a PCP-tétel új, egyszerűbb bizonyításához réserősítési módszerrel [ 46] . |
| 2020 | Robin Moser és Tardos Gábor | a Lovas lokális lemma algoritmikus változatához [47] |
| 2021 | Andrey Bulatov , Jin-Yi Cai, Xi Chen, Martin Dyer, David Richerby | a kényszer-elégedettségi problémák számolási komplexitásának osztályozásával kapcsolatos munkájukért |
| Gödel- díjasok | |
|---|---|
| 1990 |
|
| 2000 | |
| 2010 |
|