| Rok
|
Meno/mená
|
Dôvod
|
|---|
| 1993 |
László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran a Charles Rackoff |
za vývoj interaktívnych dôkazových systémov.
|
| 1994 |
Johan Håstad |
za exponenciálny dolný odhad zložitosti Booleovských okruhov s konštantnou hĺbkou.
|
| 1995 |
Neil Immerman a Róbert Szelepcsényi |
za Immermanovu-Szelepcsényiho vetu o uzavretosti triedy kontextových jazykov na komplement.
|
| 1996 |
Mark Jerrum a Alistair Sinclair |
za prácu v oblasti markovovských reťazcov.
|
| 1997 |
Joseph Halpern a Yoram Moses |
za definíciu formálneho pojmu "poznatok" v distribuovaných systémoch.
|
| 1998 |
Seinosuke Toda |
za Todovu vetu, ktorá ukázala súvislosť medzi PP a PH zložitosťou.
|
| 1999 |
Peter Shor |
za Shorov algoritmus na faktorizáciu čísel v polynomiálnom čase na kvantovom počítači.
|
| 2000 |
Moshe Y. Vardi a Pierre Wolper |
za prácu v oblasti overovania modelov pomocou konečných automatov
|
| 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 vetu a jej aplikácie v oblasti zložitosti aproximácie.
|
| 2002 |
Géraud Sénizergues |
za dôkaz, že problém ekvivalencie deterministických zásobníkových automatov je rozhodnuteľný.
|
| 2003 |
Yoav Freund a Robert Schapire |
za algoritmus AdaBoost.
|
| 2004 |
Maurice Herlihy, Mike Saks, Nir Shavit a Fotios Zaharoglou |
za aplikáciu topológie v teórii distribuovaných výpočtov.
|
| 2005 |
Noga Alon, Yossi Matias a Mario Szegedy |
za základné výsledky v oblasti algoritmov na údajových prúdoch (streamoch).
|
| 2006 |
Maníndra Agravál, Neeraj Kayal a Nitin Saxena |
za test prvočíselnosti AKS.
|
| 2007 |
Aleksandr Aleksandrovič Razborov a Steven Rudich |
za tzv. prirodzené dôkazy.
|
| 2008 |
Shanghua Teng a Daniel Spielman |
za tzv. zjemnenú analýzu algoritmov.
|
| 2009 |
Omer Reingold, Salil Vadhan a Avi Wigderson |
za tzv. zig-zag súčin grafov.
|
| 2010 |
Sanjeev Arora a Joseph S. B. Mitchell |
za algoritmus pre riešenie eukleidovského problému
|
| 2011 |
Johan Håstad |
za zavedenie nových analytických metód v teórii aproximácie obťažnosti pri výpočte problémov
|
| 2012 |
Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen |
každý za základný článok o algoritmické teórii hier
|
