Mihalisa Yannakakisa

Mihalis Yannakakis
Mihalis Yannakakis
Urodzić się	( 13.09.1953 ) 13 września 1953 Ateny , Grecja
Narodowość	Grecko - Amerykański
Alma Mater	Narodowy Uniwersytet Techniczny w Atenach Uniwersytet Princeton
Nagrody	Nagroda Knutha (2005)
Kariera naukowa
Pola	Informatyka
Instytucje	Uniwersytet Columbia
Doradca doktorski	Jeffreya Ullmana

Mihalis Yannakakis ( grecki : Μιχάλης Γιαννακάκης , urodzony 13 września 1953 w Atenach , Grecja ) jest profesorem informatyki na Uniwersytecie Columbia . Jest znany ze swojej pracy w dziedzinie złożoności obliczeniowej , baz danych i innych pokrewnych dziedzin. W 2005 roku zdobył nagrodę Donalda E. Knutha .

Edukacja i kariera

Yannakakis urodził się w Atenach w Grecji w 1953 roku i uczęszczał do Varvakeio High School w celu wczesnej edukacji. Ukończył Narodowy Uniwersytet Techniczny w Atenach w 1975 roku, uzyskując dyplom z inżynierii elektrycznej, a następnie uzyskał doktorat z informatyki na Uniwersytecie Princeton w 1979 roku. Jego praca doktorska nosiła tytuł „Złożoność maksymalnych problemów z podgrafami”.

W 1978 roku dołączył do Bell Laboratories i od 1991 do 2001 roku pełnił funkcję Dyrektora Działu Badań nad Zasadami Informatyki, kiedy to opuścił laboratoria Bella i dołączył do Avaya Laboratories. Tam pełnił funkcję dyrektora Departamentu Badań nad Zasadami Informatyki do 2002 roku.

W 2002 roku rozpoczął pracę na Uniwersytecie Stanforda , gdzie był profesorem informatyki, i opuścił go w 2003 roku, aby w 2004 roku dołączyć do Uniwersytetu Columbia , gdzie obecnie pracuje jako profesor informatyki Percy K. i Vida LW Hudson .

W latach 1992-2003 Yannakakis zasiadał w radzie redakcyjnej SIAM Journal on Computing i był redaktorem naczelnym w latach 1998-2003. Był także członkiem rady redakcyjnej Journal of the ACM w latach 1986-2000. Inne członkostwo w radach redakcyjnych obejmuje 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 Sympozjum IEEE na temat podstaw informatyki .

Od czerwca 2020 r. Jego publikacje były cytowane blisko 35 000 razy, a jego indeks h wynosi 93.

Badania

Yannakakis jest znany ze swojego wkładu w informatykę w dziedzinie teorii złożoności obliczeniowej , teorii baz danych , weryfikacji i testowania wspomaganego komputerowo oraz algorytmicznej teorii grafów .

Wśród jego wkładów w teorię złożoności znajdują się dwie prace dotyczące teorii PCP i twardości aproksymacji . Na dorocznym sympozjum ACM na temat teorii informatyki w 1988 r. Yannakakis i Christos Papadimitriou wprowadził definicje klas złożoności Max-NP i Max-SNP. Max-NP i Max-SNP (która jest podklasą Max-NP) zawierają wiele 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 środowisku naukowym w przybliżeniu szeregu problemów optymalizacyjnych, w tym 3SAT , problemu zestawu niezależnego i problemu komiwojażera .

Yannakakis i Carsten Lund przedstawili szereg ustaleń dotyczących twardości przybliżeń obliczeniowych na dorocznym sympozjum ACM na temat teorii informatyki w 1993 r. Odkrycia te pokazały trudność w wydajnym obliczeniu przybliżonych rozwiązań wielu problemów minimalizacji, takich jak kolorowanie wykresów i pokrywanie zbiorów . Biorąc pod uwagę mało prawdopodobny scenariusz, w którym NP-trudne, takie jak kolorowanie wykresów i pokrywanie zbiorów, zostałyby optymalnie rozwiązane w czasie wielomianowym , było wiele prób opracowania dla nich skutecznych rozwiązań aproksymacyjnych; wyniki uzyskane przez Yannakakisa i Carstena dowiodły nieprawdopodobieństwa wykonania tego zadania.

W dziedzinie teorii baz danych jego wkład obejmuje zainicjowanie badań nad acyklicznymi bazami danych i blokowaniem niedwufazowym. Acykliczne schematy baz danych to schematy, które zawierają pojedynczą acykliczną zależność łączenia (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 miały: na przykład zdolność 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 schematów.

W odniesieniu do blokowania niedwufazowego Yannakakis pokazał, jak wiedza o strukturze bazy danych i formach różnych transakcji na niej wykonywanych może być wykorzystana do ustalenia, czy dana polityka blokowania jest bezpieczna, czy nie. Powszechnie stosowane zasady blokowania dwufazowego (2PL) składają się z dwóch etapów – odpowiednio blokowania i odblokowywania obiektów – i aby uniknąć takiej polityki, konieczne jest narzucenie pewnej struktury podmiotom bazy danych; Wyniki Yannakakisa pokazują, w jaki sposób, wybierając hipergraf przypominając 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, a polityki te można sklasyfikować zgodnie z łącznością wspomnianego powyżej hipergrafu, przy czym polityki 2PL są tylko jednym z nich. Następnie Yannakakis wykazał, że dla naturalnej klasy zasad bezpiecznego blokowania (polityki L) wolność od zakleszczeń jest określana wyłącznie na podstawie kolejności, w jakiej podmioty są udostępniane przez transakcje, i z tego wyprowadzone są proste warunki, które gwarantowałyby wolność od zakleszczeń dla polityka L.

Wniósł również wkład w obszar weryfikacji i testowania wspomaganego komputerowo, gdzie położył podwaliny pod rygorystyczne algorytmy i teorię złożoności w tej dziedzinie. Niektóre z jego wkładów obejmują projektowanie efektywnych pamięciowo algorytmów do weryfikacji właściwości czasowych programów o skończonych stanach, określanie złożoności testowania, czy programy spełniają swoje specyfikacje wyrażone w logice czasowej w czasie liniowym oraz sprawdzenie, czy model z ograniczeniami czasowymi spełnia daną właściwość czasową. Wraz z Alexem Groce i Doronem Peledem wprowadził adaptacyjne sprawdzanie modelu, pokazując, że w przypadku niespójności między systemem a odpowiadającym mu modelem wyniki weryfikacji można wykorzystać do ulepszenia modelu. Wniósł również wkład w badania nad Message Sequence Charts (MSC), gdzie wykazano, że słaba realizowalność jest nierozstrzygalna dla ograniczonych grafów MSC i że bezpieczna realizacja jest w EXPSPACE , wraz z innymi interesującymi wynikami związanymi z weryfikacją grafów MSC .

Nagrody i uznanie

Yannakakis jest członkiem Narodowej Akademii Inżynierii i Narodowej Akademii Nauk . Otrzymał siódmą nagrodę Knutha za wkład w informatykę teoretyczną. Otrzymał również nagrodę Bell Labs Distinguished Member of Technical Staff Award oraz Bell Labs President's Gold Award odpowiednio w 1985 i 2000 roku. Jest członkiem ACM, a także członkiem Bell Laboratories . Został wybrany członkiem Amerykańskiej Akademii Sztuki i Nauki (AAAS) w 2020 roku.

Linki zewnętrzne

• Strona główna w Kolumbii