Rok
|
Jména
|
Příspěvek
|
---|
1993
|
László Babai ( Maďarsko ) a Shlomo Moran ( Izrael ), Shafi Goldwasser ( Izrael / USA ), Silvio Micali ( Itálie / USA ) a Charles Rackoff ( USA )
|
Vývoj konceptu interaktivního zkušebního systému
|
1994
|
Johan Håstad ( Švédsko )
|
Svorky týkající se problémů s booleovským obvodem , a zejména s paritní funkcí
|
1995
|
Neil Immerman ( USA ) a Róbert Szelepcsényi ( Slovensko )
|
Jejich věta spojující třídy NSPACE a co-NSPACE
|
1996
|
Mark Jerrum ( Velká Británie ) a Alistair Sinclair ( Velká Británie )
|
Jejich práce na Markovových řetězcích a trvalé přiblížení
|
1997
|
Joseph Halpern ( USA ) a Yoram Moses ( Izrael )
|
Vývoj pojmu informace v kontextu distribuovaných systémů
|
1998
|
Seinosuke Toda ( Japonsko )
|
Jeho věta týkající se tříd složitosti PP a PH
|
1999
|
Peter Shor ( Spojené státy )
|
Algoritmus Shor , který umožňuje k číslům faktoru v polynomiálním čase na kvantový počítač
|
2000
|
Moshe Vardi ( Izrael ) a Pierre Wolper ( Belgie )
|
Jejich práce na časové logice v kontextu konečných automatů
|
2001
|
Sanjeev Arora ( USA ), Uriel Feige ( Izrael ), Shafi Goldwasser ( Izrael / USA ), Carsten Lund ( Dánsko ), László Lovász ( Maďarsko / USA ), Rajeev Motwani ( Indie ), Shmuel Safra ( Izrael ), Madhu Súdán ( Spojené státy ) a Mario Szegedy ( Maďarsko / Spojené státy )
|
Jejich věta o PCP
|
2002
|
Géraud Sénizergues ( Francie )
|
Prokázaly Rozhodnutelnost rovnosti dvou jazyků uznávaný deterministické
Skládaný automatů |
2003
|
Yoav Freund ( Izrael ) a Robert Schapire ( Spojené státy )
|
Algoritmus AdaBoost ve strojovém učení
|
2004
|
Maurice Herlihy ( USA ), Michael Saks ( USA ), Nir Shavit ( Izrael ), Fotios Zaharoglou ( Řecko )
|
Aplikace konceptů topologie na distribuované výpočty
|
2005
|
Noga Alon ( Izrael ), Yossi Matias ( Izrael ) a Mario Szegedy ( Maďarsko )
|
Jejich příspěvky k algoritmům dolování datových toků
|
2006
|
Manindra Agrawal ( Indie ), Neeraj Kayal ( Indie ) a Nitin Saxena ( Indie )
|
Test prvosti AKS
|
2007
|
Alexandre Razborov ( Rusko ) a Steven Rudich ( Spojené státy )
|
Jejich klíčový článek o přírodních důkazech
|
2008
|
Shang-Hua Teng ( Čína ) a Daniel Spielman ( Spojené státy )
|
Algoritmus hladký analýza ( vyhlazené analýza ) |
2009
|
Omer Reingold ( Izrael ), Salil Vadhan ( USA ) a Avi Wigderson ( Izrael )
|
Klikatá produkt grafů
|
2010
|
Sanjeev Arora ( Spojené státy ) a Joseph SB Mitchell ( Spojené státy )
|
Polynom aproximace schéma na problém obchodního cestujícího v případě euklidovské
|
2011
|
Johan Håstad ( Švédsko )
|
Výsledky obtížnosti aproximace spojené s teorémem PCP |
2012
|
Elias Koutsoupias ( Řecko ), Christos Papadimitriou ( Řecko ), Noam Nisan ( Izrael ), Amir Ronen ( Izrael ), Tim Roughgarden ( USA ) a Éva Tardos ( Maďarsko )
|
Tvorba algoritmické teorie her
|
2013
|
Dan Boneh ( Izrael ), Matthew K. Franklin ( USA ) a Antoine Joux ( Francie )
|
Zavedení kryptografie založené na vazbě
|
2014
|
Ronald Fagin ( USA ), Amnon Lotem ( Izrael ) a Moni Naor ( Izrael )
|
Optimální agregační algoritmy |
2015 |
Shang-Hua Teng ( Čína ) a Daniel Spielman ( Spojené státy )
|
Jejich práce v digitální lineární algebře a aplikace na algoritmy grafů a teorii spektrálních grafů
|
2016 |
Stephen D. Brookes ( Spojené království ) a Peter O'Hearn ( Kanada )
|
Vynález souběžné separační logiky |
2017 |
Cynthia Dwork ( USA ), Frank McSherry ( USA ), Kobbi Nissim ( Izrael ) a Adam D. Smith ( USA )
|
Vynález rozdílné důvěrnosti
|
2018
|
Oded Regev ( Izrael )
|
Zavedení problému učení s chybami , studium jeho průměrné složitosti redukcí na problémy euklidovských sítí a jeho dopad na postkvantovou kryptografii
|
2019
|
Irit Dinur ( Izrael )
|
Pro důkaz zásadně odlišný od věty PCP , jednodušší, přímější a efektivnější.
|
2020
|
Robin A. Moser a Gábor Tardos ( Maďarsko )
|
Pro algoritmickou verzi Lovászova lokálního lemmatu .
|
2021 |
Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer ( Velká Británie ) a David Richerby
|
Klasifikace složitosti počítání (in) na problémy s omezujícími podmínkami .
|