| Michalis Yannakakis | |
|---|---|
| řecký Μιχάλης Γιαννακάκης | |
| Datum narození | 13. září 1953 (ve věku 69 let) |
| Místo narození | Atény , Řecko |
| Země | |
| Vědecká sféra |
teorie výpočetní složitosti , databáze |
| Místo výkonu práce | Kolumbijská univerzita |
| Alma mater | Athénská národní technická univerzita |
| vědecký poradce | Geoffrey Ullman |
| Ocenění a ceny |
Cena za významného člena technického personálu Bell Labs ( 1985 ) Zlatá cena prezidenta Bell Labs ( 2000 ) Cena Knuth ( 2005 ) |
Michalis Yannakakis ( řecky Μιχάλης Γιαννακάκης , anglicky Mihalis Yannakakis ; narozen 13. září 1953 , Atény , Řecko ) je řecký počítačový vědec , profesor na Kolumbijské univerzitě ( New York , USA ). Známý pro svou práci v teorii výpočetní složitosti , databázích a dalších příbuzných oborech. Vítěz Knuthovy ceny ( 2005 ). Člen Národní akademie věd USA (2018) [1] .
Michalis Giannakakis se narodil v Aténách 13. září 1953 a pro své rané vzdělání navštěvoval experimentální gymnázium Varvakio (řecky: Βαρβάκειο Πειραματικό Γυμνάσιο) v Psychiko (Athens).
V roce 1975 promoval na Národní technické univerzitě v Aténách v oboru elektrotechnika a v roce 1979 získal doktorát v oboru počítačových věd na Princetonské univerzitě ( USA ). Jeho disertační práce nesla název „ Složitost maximálních problémů podgrafů “. [2]
V roce 1978 se Michalis Giannakakis připojil k Bell Lab Corporation ( Murray Hill , New Jersey , USA ) a v letech 1991-2001. Byl ředitelem divize výzkumu základů informačních technologií. Poté opustil Bell Laboratories a nastoupil do Avaya Labs. Tam byl Giannakakis do roku 2002 ředitelem divize výzkumu základů informačních technologií .
V roce 2002 převzal Giannakakis místo profesora počítačových věd na Stanfordské univerzitě , kde zůstal až do roku 2003 .
Od roku 2004 do současnosti je profesorem informatiky na Kolumbijské univerzitě .
Od roku 1992 do roku 2003_ Giannakakis byl členem redakční rady časopisu SIAM Journal on Computing (SICOMP ) v letech 1998-2003 . byl jeho šéfredaktorem. V letech 1986-2000_ _ _ působil také v redakční radě Journal of the Association for Computing Machinery . Michalis Giannakakis je členem redakčních rad řady dalších časopisů, včetně Journal of Computer and System Sciences , Journal of Combinatorial Optimization a Journal of Complexity . Působil také v dohodovacích výborech a předsedal různým konferencím, jako je ACM Symposium on Principles of Database Systems (PODS) a IEEE Symposium on Foundations of Computer Science.
K listopadu 2015 byly vědecké publikace Michalise Giannakakise citovány asi 27 000krát a jeho h-index je 86. [3]
Michalis Giannakakis je známý svými příspěvky do počítačové vědy v oblastech, jako je teorie výpočetní složitosti , teorie databází , automatizované ověřování a testování a teorie algoritmických grafů .
Zvláštní místo mezi cennými úspěchy vědce v oblasti teorie složitosti zaujímají dvě klíčové práce na témata teorie pravděpodobnostně ověřitelných důkazů a složitost aproximace . V roce 1988 Michalis Giannakakis a Christos Papadimitriou představili definice tříd složitosti Max-NP a Max-SNP (což je podtřída Max-NP) na každoročním Symposiu o teorii počítání financovaném Asociací pro výpočetní stroje (AUT) a obsahujícím řadu zajímavých optimalizačních problémů. Giannakakis a Papadimitriou ukázali, že tyto problémy mají určitou omezenou chybu. S pomocí těchto zjištění bylo možné vysvětlit nedostatek pokroku zaznamenaný ve výzkumné komunitě ve studiu aproximace řady optimalizačních problémů, včetně problému „ 3 -uspokojitelnosti “ , problému nezávislých množin a problém cestujícího prodejce . [čtyři]
V roce 1993 na pravidelném sympoziu AVT o teorii počítání představili Michalis Giannakakis a Karsten Lund řadu důležitých závěrů týkajících se problematiky výpočetních aproximací . Tyto výsledky ukázaly, že je obtížné efektivně vypočítat přibližná řešení řady problémů minimalizace, jako je případ zbarvení grafu a problém pokrytí množin . Vzhledem k nepravděpodobnosti, že takové NP-těžké problémy budou optimálně vyřešeny v polynomiálním čase , bylo učiněno mnoho pokusů vyvinout pro ně účinná přibližná řešení. Výsledky získané Giannakakisem a Carstenem prokázaly, že tohoto cíle pravděpodobně nebude dosaženo. [5]
V oblasti teorie databází je hlavním přínosem Michalise Giannakakise iniciace výzkumu acyklických databází a nedvoufázového blokování. Acyklická databázová schémata jsou schémata, která obsahují jednu závislost acyklického připojení a sadu funkčních závislostí. [6] Řada výzkumníků, včetně Giannakakise, si všimla užitečnosti těchto schémat a prokázala mnoho užitečných vlastností, které mají: schopnost řešit mnoho problémů založených na acyklických schématech v polynomiálním čase, a to navzdory skutečnosti, že problémem může být NP -kompletní pro ostatní schémata. [7]
Byla mu udělena Knuthova cena ( 2005 ) za význam, vliv a ohromující rozsah jeho příspěvku k teoretickým základům výpočetní techniky a také obdržel dvě ocenění od Bell Labs: Cenu pro významného člena technického personálu ( 1985 ) a Zlaté ocenění prezidenta ( 2000 ). Je členem Asociace pro výpočetní techniku a výzkumného centra v Bell Labs .
| Vítězové Knuthovy ceny | |
|---|---|