Ravindran Kannan

Ravi Kannan

Popis tohoto obrázku, také komentován níže

Ravi Kannan na své stránce na Yale University Klíčové údaje

Narození	12. března 1953 Chennai ( Indie )
Domov	Bangalore
Oblasti	Počítačová věda
Diplom	Cornell University
Dozorce	Leslie Earl Trotter
Ocenění	Cena Fulkersona (1991) Cena Knutha (2011),

Ravindran Kannan , zvaný Ravi , narozen dne12. března 1953v Chennai je počítačový vědec a matematik. Je hlavním výzkumným pracovníkem společnosti Microsoft Research India, kde vede Algorithmics Research Group. Je také prvním asistentem fakulty výpočetní techniky a oddělení automatizace na Indian Institute of Science v Bangalore .

Životopis

Kannan byl vzděláván na Indickém technologickém institutu v Bombaji a v roce 1980 získal titul Ph.D. z Cornell University pod dohledem Leslie Earl Trotter s názvem Velikost čísel v analýze určitých algoritmů . Učil na Massachusetts Institute of Technology , poté působil jako profesor na Carnegie-Mellon University a poté profesorem informatiky a aplikované matematiky na Yale University na židli Williama K. Lanmana Jr. a nakonec se připojil k Microsoftu .

Výzkum

Výzkumné oblasti

Jeho výzkumné zájmy zahrnují algoritmiku , teoretickou informatiku a diskrétní matematiku a také optimalizaci . Jeho práce se zaměřuje na vývoj efektivních algoritmů pro problémy matematické povahy a často geometrické, které vznikají v informatice. Pracoval na algoritmech čísel lineární optimalizace v celých číslech , geometrii čísel , náhodných procházkách v prostorech libovolné dimenze, randomizovaných algoritmech pro lineární algebru a algoritmech učení pro konvexní množiny .

S Alan M. Frieze (v) , Kannan vyvinul algoritmické verzi „ lemma pravidelností z Szemerédi “. Zavádějí slabé lemma pravidelnosti, které se stává důležitým kombinatorickým nástrojem pro různé typy algoritmů ( algoritmus dolování datových toků , limity grafů, sublearní algoritmy ).

V roce 1991 Kannan publikoval efektivní algoritmus (tj. V polynomiálním čase) k řešení „ problému s mincí “, nazývaného také „ Frobeniova úloha “: jde o určení největšího celého čísla (tzv. Frobeniova čísla), které nelze reprezentovat jako součet čísel převzatých z dané množiny. Například pokud máme coiny s jednotkovou hodnotou 3 a 5, je Frobeniovo číslo 7: jakékoli celé číslo n větší lze zapsat jako n = 3 i + 5 j (s přirozenými čísly i a j ). V tomto jednoduchém případě dvou čísel a a b je explicitní vzorec, často nesprávně přisuzovaný Sylvestrovi , součástí matematického folklóru (ne) počet Frobenius je ab - ab .

Hlavní příspěvky

Mezi jeho hlavní příspěvky, které mu vynesly ocenění, kterých je držitelem, patří:

Martin Dyer , Alan M. Frieze a Ravindran Kannan , „ Náhodný algoritmus polynomiálního času pro přiblížení objemu konvexních těles “, Journal of ACM , sv. 38, n o 1,1991, str. 1-17
Alan M. Frieze a Ravindran Kannan , „ Jednoduchý algoritmus pro konstrukci Szemerédiho oddílu pravidelnosti “, Electronic Journal of Combinatorics , sv. 6,1999( číst online )Tento článek byl představen na sympoziu FOCS v roce 1966 pod názvem Lemita pravidelnosti a aproximační schémata pro husté problémy .

Další publikace (výběr)

Ravindran Kannan a László Lovász , „ Pokrytí konvexních těles bez minima a mřížkového bodu “, Annals of Mathematics , sv. 128,1988, str. 577–602
Ravindran Kannan , „ Lattice translates of a polytop and the Frobenius problem “, Combinatorica , sv. 12,1992, str. 161-177
A. Blum (en) , Alan M. Frieze , Ravindran Kannan a S. Vempala , „ Algoritmus polynomiálního času pro učení hlučných lineárních prahových funkcí “, Algorithmica , sv. 22,1998, str. 35–52
P. Drineas , Alan M. Frieze , Ravindran Kannan , S. Vempala a V. Vinay , „ Shlukování ve velkých grafech a matricích “, Sborník sympozia o diskrétním algoritmu ,1999

Ceny a ocenění

Cena Distinguished Alumnus od Indického technologického institutu v Bombaji v roce 1999.
Hostující řečník na IEEE Foundations of Computer Science Symposium v roce 1997.
Vítěz ceny Fulkersonovy ceny za diskrétní matematiku z roku 1991 s Martinem Dyerem a Alanem M. Friezem za článek o objemu výše uvedených konvexních množin .
Ravi Kannan je držitelem Knuthovy ceny za rok 2011, která mu byla udělena „za vývoj dalekosáhlých algoritmických technik k řešení dlouhotrvajících algoritmických problémů“.

Poznámky a odkazy

Kdo je kdo na hranicích vědy a techniky 1985
(in) „ Ravindran Kannan “ na webových stránkách projektu Mathematics Genealogy Project .
Microsoft Researcher obdrží ACM SIGACT Knuth Prize „ Archived Copy“ (verze 29. dubna 2011 v internetovém archivu )