Gödelova cena

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é ceny

Rok	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í hloubkou
1995	Neil Immerman a Róbert Szelepcsényi	za Immermanovu-Szelepcsényiho větu
1996	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émech
1998	Seinosuke Toda	za Todovu větu
1999	Peter Shor	za Shorův algoritmus na faktorizaci čísel v polynomiálním čase na kvantovém počítači
2000	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 aproximace
2002	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ůkazy
2008	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ému
2011	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 her
2013	Antoine Joux, Dan Boneh a Matthew K. Franklin	za pokrok v kryptografii
2014	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

• Obrázky, zvuky či videa k tématu Gödelova cena na Wikimedia Commons
• Oficiální stránka ceny