Gödelova cena je vědecké ocenění udělované od roku 1993 každoročně za nejlepší odborné články z oblasti teoretické informatiky.
Uděluje ji European Association for Theoretical Computer Science a Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory. Součástí ceny je finanční odměna ve výši 5000$. Cena je pojmenována po rakouském matematikovi a logikovi Kurtu Gödelovi.
+Nositelé cenyRok Jméno Zdůvodnění1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran a Charles Rackoff za vývoj interaktivních důkazových systémů1994 Johan Håstad za exponenciální odhad složitosti Booleových okruhů s konstantní hloubkou1995 Neil Immerman a Róbert Szelepcsényi za Immermanovu-Szelepcsényiho větu1996 Mark Jerrum a Alistair Sinclair za práci v oblasti markovových řetězců1997 Joseph Halpern a Yoram Moses za definici formálního pojmu "poznatek" v distribuovaných systémech1998 Seinosuke Toda za Todovu větu1999 Peter Shor za Shorův algoritmus na faktorizaci čísel v polynomiálním čase na kvantovém počítači2000 Moshe Y. Vardi a Pierre Wolper za práci v oblasti ověřování modelů pomocí konečných automatů2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Radžív Mótvání, Shmuel Safra, Madhu Sudan a Mario Szegedy za PCP větu a její aplikace v oblasti složitosti aproximace2002 Géraud Sénizergues za důkaz, že problém ekvivalence deterministických zásobníkových automatů je rozhodnutelný2003 Yoav Freund a Robert Schapire za algoritmus AdaBoost.2004 Maurice Herlihy, Mike Saks, Nir Shavit a Fotios Zaharoglou za aplikaci topologie v teorii distribuovaných výpočtů2005 Noga Alon, Yossi Matias a Mario Szegedy za základní výsledky v oblasti algoritmů na datových proudech (streamech)2006 Maníndra Agravál, Neeraj Kayal a Nitin Saxena za test prvočíselnosti AKS.2007 Aleksandr Aleksandrovič Razborov a Steven Rudich za tzv. přirozené důkazy2008 Shanghua Teng a Daniel Spielman za tzv. zjemněnou analýza algoritmů2009 Omer Reingold, Salil Vadhan a Avi Wigderson za tzv. zig-zag součin grafů2010 Sanjeev Arora a Joseph S. B. Mitchell za algoritmus při řešení eukleidovského problému2011 Johan Håstad za zavedení nových analytických metod v teorii aproximace obtížnosti při výpočtu problémů2012 Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen za základní články o algoritmické teorii her2013 Antoine Joux, Dan Boneh a Matthew K. Franklin za pokrok v kryptografii2014 Ronald Fagin, Amnon Lotem a Moni Naor za návrh nových algoritmů2015 Daniel A. Spielman a Shang-Hua Teng 2016 Stephen Brookes a Peter W. O'Hearn
Externí odkazy
Oficiální stránka ceny
Kategorie:Matematická ocenění Kategorie:Informatická ocenění Kategorie:Vzniklo 1993