Mihalis Yannakakis - Mihalis Yannakakis
Mihalis Yannakakis | |
|---|---|
 Mihalis Yannakakis
| |
| Urodzić się |
13 września 1953 |
| Narodowość | grecki – amerykański |
| Alma Mater |
Narodowy Uniwersytet Techniczny w Atenach Uniwersytet Princeton |
| Nagrody | Nagroda Knutha (2005) |
| Kariera naukowa | |
| Pola | Informatyka |
| Instytucje | Uniwersytet Columbia |
| Doradca doktorski | Jeffrey Ullman |
Mihalis Yannakakis ( gr . Μιχάλης Γιαννακάκης ; ur. 13 września 1953 r. w Atenach , Grecja ) jest profesorem informatyki na Uniwersytecie Columbia . Jest znany ze swojej pracy w zakresie złożoności obliczeniowej , baz danych i innych pokrewnych dziedzin. Zdobył nagrodę Donalda E. Knutha w 2005 roku.
Edukacja i kariera
Yannakakis urodził się w Atenach w Grecji w 1953 roku i uczęszczał do liceum Varvakeio ze względu na swoją wczesną edukację. Ukończył Narodowy Uniwersytet Techniczny w Atenach w 1975 roku, uzyskując dyplom z elektrotechniki, a następnie uzyskał stopień doktora. Doktoryzował się z informatyki na Uniwersytecie Princeton w 1979 roku. Jego rozprawa nosiła tytuł „The Complexity of Maximum Subgraph Problems”.
W 1978 roku dołączył do Bell Laboratories i pełnił funkcję dyrektora Działu Badań Zasad Obliczeniowych, począwszy od 1991 do 2001 roku, kiedy to opuścił laboratoria Bell i dołączył do Avaya Laboratories. Tam pełnił funkcję dyrektora Departamentu Badań Zasad Obliczeniowych do 2002 roku.
W 2002 dołączył do Stanford University, gdzie był profesorem informatyki, a odszedł w 2003, aby dołączyć do Columbia University w 2004, gdzie obecnie jest profesorem informatyki Percy K. i Vida LW Hudson .
W latach 1992-2003 Yannakakis był członkiem rady redakcyjnej czasopisma SIAM Journal on Computing, a w latach 1998-2003 był redaktorem naczelnym. W latach 1986-2000 był także członkiem rady redakcyjnej Journal of the ACM . Inni członkowie rady redakcyjnej to Journal of Computer and System Sciences , Journal of Combinatorial Optimization i Journal of Complexity. Zasiadał również w komitetach konferencyjnych i przewodniczył różnym konferencjom, takim jak ACM Symposium on Principles of Database Systems oraz IEEE Symposium on Foundations of Computer Science .
Według stanu na czerwiec 2020 r. jego publikacje były cytowane blisko 35 000 razy, a jego indeks h wynosi 93.
Badania
Yannakakis znany jest ze swoich składek do informatyki w dziedzinie teorii złożoności obliczeniowej , teorii baz danych , weryfikacji komputerowego wspomagania testowania i algorytmicznej teorii grafów .
Wśród jego wkładu w teorię złożoności są dwa artykuły dotyczące teorii PCP i twardości aproksymacji . Na Dorocznym Sympozjum Teorii Obliczeń ACM w 1988 r. Yannakakis i Christos Papadimitriou wprowadzili definicje klas złożoności Max-NP i Max-SNP. Max-NP i Max-SNP (która jest podklasą Max-NP) zawierają szereg interesujących problemów optymalizacyjnych, a Yannakakis i Papadimitriou wykazali, że problemy te mają pewien ograniczony błąd. Odkrycia te były w stanie wyjaśnić brak postępu, jaki zaobserwowano w społeczności badawczej w zakresie przybliżenia wielu problemów optymalizacyjnych, w tym 3SAT , problemu Independent Set oraz Traveling Salesman Problem .
Yannakakis i Carsten Lund przedstawili szereg ustaleń dotyczących twardości przybliżeń obliczeniowych na dorocznym sympozjum teorii obliczeń komputerowych ACM w 1993 roku. Odkrycia te wykazały trudności w wydajnym obliczaniu przybliżonych rozwiązań wielu problemów związanych z minimalizacją, takich jak kolorowanie wykresów i pokrywanie zbiorów . Biorąc pod uwagę mało prawdopodobny scenariusz, w którym problemy NP-trudne , takie jak kolorowanie grafów i pokrywanie zbiorów, byłyby rozwiązywane optymalnie w czasie wielomianowym , było wiele prób opracowania dla nich efektywnych rozwiązań przybliżających; wyniki uzyskane przez Yannakakisa i Carstena wykazały małe prawdopodobieństwo realizacji tego zadania.
Jego wkład w dziedzinie teorii baz danych obejmuje rozpoczęcie badań nad acyklicznymi bazami danych i niedwufazowym blokowaniem. Acykliczne schematy baz danych to schematy, które zawierają pojedynczą zależność łączenia acyklicznego ( zależność łączenia to relacja rządząca łączeniem tabel bazy danych) oraz zbiór zależności funkcjonalnych; wielu badaczy, w tym Yannakakis, zwróciło uwagę na przydatność tych schematów, demonstrując wiele użytecznych właściwości, jakie posiadały: na przykład zdolność do rozwiązywania wielu problemów opartych na schematach acyklicznych w czasie wielomianowym, podczas gdy problem mógł z łatwością być NP- kompletne dla innych programów.
W odniesieniu do blokowania niedwufazowego Yannakakis zademonstrował, w jaki sposób wiedza o strukturze bazy danych i formach różnych transakcji wykonywanych na nich może być wykorzystana do ustalenia, czy dana polityka blokowania jest bezpieczna, czy nie. Powszechnie stosowana polityka dwufazowego blokowania (2PL) składa się z dwóch etapów - odpowiednio dla blokowania i odblokowywania jednostek - i aby uniknąć takiej polityki konieczne jest narzucenie pewnej struktury na jednostki bazy danych; Wyniki Yannakakisa pokazują, w jaki sposób, wybierając hipergraf przypominający strukturę ograniczeń spójności bazy danych, polityka blokowania, która odwiedza jednostki wzdłuż ścieżek tego hipergrafu, będzie bezpieczna. Taka polityka nie musi być dwufazowa i polityki te mogą być klasyfikowane zgodnie z łącznością wspomnianego powyżej hipergrafu, przy czym polityki 2PL są tylko jednym z nich. Yannakakis wykazał następnie, że w przypadku naturalnej klasy zasad bezpiecznych blokad (polityki L), wolność od zakleszczeń jest określana wyłącznie na podstawie kolejności, w jakiej podmioty są dostępne dla transakcji, i na podstawie tych wyprowadzonych prostych warunków, które gwarantowałyby wolność od zakleszczeń dla polisa L.
Wniósł również wkład w obszar komputerowej weryfikacji i testowania, gdzie położył rygorystyczne podstawy algorytmiczne i teoretyczne złożoności tej dziedziny. Niektóre z jego wkładów obejmują projektowanie wydajnych pamięciowo algorytmów do weryfikacji właściwości czasowych programów skończonych, określanie złożoności testowania, czy programy spełniają swoje specyfikacje wyrażone w logice temporalnej czasu liniowego oraz weryfikację, że model z ograniczeniami czasowymi spełnia daną właściwość czasową. Wraz z Alexem Groce i Doronem Peledem wprowadził Adaptive Model Checking, pokazując, że gdy występują niespójności między systemem a odpowiadającym mu modelem, wyniki weryfikacji można wykorzystać do ulepszenia modelu. Brał również udział w badaniach nad Message Sequence Charts (MSC), gdzie wykazano, że słaba realizowalność jest nierozstrzygalna dla ograniczonych grafów MSC i że bezpieczna realizowalność jest w EXPSPACE , wraz z innymi interesującymi wynikami związanymi z weryfikacją grafów MSC .
Nagrody i uznanie
Yannakakis jest członkiem zarówno Narodowej Akademii Inżynierii, jak i Narodowej Akademii Nauk . Za swój wkład w informatykę teoretyczną otrzymał siódmą nagrodę Knutha . Otrzymał również nagrodę Bell Labs Distinguished Member of Technical Staff Award oraz Gold Award Bell Labs President's, odpowiednio w 1985 i 2000 roku. Jest członkiem ACM, a także Fellow of Bell Laboratories . Został wybrany na członka Amerykańskiej Akademii Sztuk i Nauk (AAAS) w 2020 roku.