Gödelpriset är Kurt Gödel -priset i beräkningssystemteori , som årligen delas ut av ACM SIGACT , ( Special Interest Group on Algorithms and Computation Theory ) och EATCS , ( European Association for Theoretical Computer Science ) för enastående arbete med logik och teoretisk datavetenskap .
Priset har delats ut sedan 1993 och åtföljs av en kontant utmärkelse på $ 5 000 [1] . Priset äger rum antingen på det amerikanska symposiet STOC , ( Symposium on Theory of Computing ), eller på den europeiska konferensen ICALP , ( International Colloquium on Automata, Languages and Programming ). Huvudkravet för verket är datumet för den första publiceringen - endast verk som inte är äldre än 14 år får nomineras.
| År | namn | Anteckningar |
|---|---|---|
| 1993 | Laszlo Babai , Shafi Goldwasser , Silvio Micali , Shlomo Moran och Charles Rakoff | för att utveckla interaktiva bevissystem [2] [3] . |
| 1994 | Johan Hostad | för att bevisa en exponentiell nedre gräns för paritetsräkning med hjälp av booleska scheman med konstant djup [4] [5] . |
| 1995 | Neil Immerman , Robert Shelepcheni | för Immermann-Shelepcheni-satsen ( beräkningskomplexitetsteori ) [6] [7] . |
| 1996 | Mark Jerram , Alistair Sinclair | för hans forskning om Markov-kedjor och approximationen av matrisernas permanenta [8] [9] . |
| 1997 | Joseph Halpern , Yoram Moses | för den formella definitionen av begreppet "kunskap" i distribuerade miljöer [10] [11] . |
| 1998 | Seinosuke Toda | för Todas teorem , som visade sambandet mellan komplexitetsklasserna PP och PH [12] [13] . |
| 1999 | Peter Shore | för Shors algoritm för att faktorisera tal i en polynomisk tid på en kvantdator [14] [15] . |
| 2000 | Moshe Vardy , Pierre Wolper | för hans forskning om modellkontroll med finita automater [16] [17] . |
| 2001 | Sanjeev Arora , Uriel Feige , Shafi Goldwasser , Karsten Lund Laszlo Lovas , Rajiv Motwani Shmuel Safra , Sudan , Mario Szegedi | för PCP-satsen och dess tillämpning [18] [19] . |
| 2002 | Jéro Senizerg | för att bevisa lösbarheten av ekvivalensen av deterministiska pushdown-automater [20] [21] . |
| 2003 | Yoav Freund och Robert Shapire | för AdaBoost-algoritmen [22] [23] . |
| 2004 | Maurice Herlihy , Michael Sachs Nir Shavit och Fotios Zaharoglu | för tillämpning av topologi på teorin om distribuerad beräkning [24] [25] . |
| 2005 | Noga Alon , Yossi Matias , Mario Szegedi | för nyskapande forskning inom området för streamingalgoritmer [26] [27] . |
| 2006 | Manindra Agrawal , Niraj Kayal , Nitin Saxena | för Agrawal-Kayala-Sachsen-testet [28] [29] . |
| 2007 | Alexander Razborov , Steven Rudich | för " naturliga bevis " [30] [31] . |
| 2008 | Teng Shanhua , Daniel Speelman | för " smidig analys " av algoritmer [32] . |
| 2009 | Omer Reingold , Salil Wadhan , Avi Wigderson | för sicksackprodukten av grafer och att hitta en deterministisk algoritm , logaritmisk i minnet , för att lösa det oriktade st-anslutningsproblemet[33] . |
| 2010 | Sanjiv Arora , Joseph Mitchell | för upptäckten av det tidspolynomiska approximationsschemat (PTAS) för det euklidiska resandeförsäljarproblemet [34] . |
| 2011 | Johan Hostad | för att bevisa icke-närbarhet för olika kombinatoriska problem [35] . |
| 2012 | Elias Koutsoupias , Christos Papadimitriou , Tim Roukhgarden , Eva Tardos , Noam Nisan , Amir Ronen | för hans bidrag till att förstå hur själviskt beteende hos användare och tjänsteleverantörer påverkar beteendet hos Internet och andra komplexa datorsystem [36] . |
| 2013 | Antoine Joux , Dan Bonet , Matthew C. Franklin | för hans arbete med kryptografi [37] [38] . |
| 2014 | Ronald Fagin , Amnon Lotem , Moni Naor | för optimala aggregeringsalgoritmer för Middleware [39] . |
| 2015 | Daniel Spielman , Teng Shanhua | för en serie artiklar om snabb lösning av linjära ekvationssystem [40] [41] . |
| 2016 | Stephen Brooks , Peter O'Hearn | för utveckling av en parallell partitioneringslogik [42] . |
| 2017 | Cynthia Dwork , Frank McSherry , Kobe Nissim , Adam D. Smith | Differentiell integritet [43] . |
| 2018 | Oded Regev | Lärande med fel [44] . |
| 2019 | Irit Dinur [45] | för ett nytt, enklare bevis på PCP-satsen genom spaltförstärkningsmetoden [ 46] . |
| 2020 | Robin Moser och Gabor Tardos | för den algoritmiska versionen av Lovas lokala lemma [47] |
| 2021 | Andrey Bulatov , Jin-Yi Cai, Xi Chen, Martin Dyer, David Richerby | för deras arbete med klassificeringen av räknekomplexiteten för problem med begränsningstillfredsställelse |
| Gödelpristagare _ | |
|---|---|
| 1990 |
|
| 2000 | |
| 2010 |
|