Interested Article - Яннакакис, Михалис

Миха́лис Яннака́кис ( греч. Μιχάλης Γιαννακάκης , англ. Mihalis Yannakakis ; род. 13 сентября 1953 , Афины , Греция ) — греческий учёный в области компьютерных наук , профессор Колумбийского университета ( Нью-Йорк , США ). Известен своими работами в области теории сложности вычислений , баз данных и других смежных областях. Лауреат Премии Кнута ( 2005 ). Член Национальной академии наук США (2018) .

Образование и карьера

Михалис Яннакакис родился в Афинах 13 сентября 1953 года и для раннего образования посещал (греч. Βαρβάκειο Πειραματικό Γυμνάσιο) в Психико (Афины).

В 1975 году окончил Афинский национальный технический университет с дипломом в области электротехники, а в 1979 году получил степень доктора философии в области компьютерных наук в Принстонском университете ( США ). Его диссертация называлась « The Complexity of Maximum Subgraph Problems ».

В 1978 году Михалис Яннакакис присоединился к корпорации Лаборатории Белла ( , Нью-Джерси , США ) и в 1991—2001 гг. был директором Отдела исследований основ информационных технологий. Затем он покинул Bell Laboratories и присоединился к Avaya Labs. Там Яннакакис был директором Отдела исследований основ информационных технологий до 2002 года.

В 2002 году Яннакакис занял пост профессора компьютерных наук в Стэнфордском университете , где оставался до 2003 года.

С 2004 года и по настоящее время работает профессором компьютерных наук в Колумбийском университете .

С 1992 по 2003 гг. Яннакакис работал в редакционной коллегии журнала SIAM Journal on Computing (SICOMP), в 1998 - 2003 гг. был его главным редактором. В 1986 - 2000 гг. он также работал в редакции Журнала Ассоциации вычислительной техники . Михалис Яннакакис работает в редакционных коллегиях ряда других журналов, включая Журнал компьютерных и системных наук ( англ. Journal of Computer and System Sciences ), Журнал комбинаторной оптимизации ( англ. Journal of Combinatorial Optimization ) и Журнал сложности ( англ. Journal of Complexity ). Он также был членом согласительных комитетов и возглавлял различные конференции, такие как ACM Symposium on Principles of Database Systems (PODS) и IEEE Symposium on Foundations of Computer Science.

По состоянию на ноябрь 2015 года, научные публикации Михалиса Яннакакиса были процитированы около 27000 раз, а его h-индекс составляет 86.

Научно-исследовательская работа

Михалис Яннакакис известен благодаря вкладу в компьютерную науку , в такие области как теория сложности вычислений , , автоматизированная верификация и тестирование, а также алгоритмическая теория графов .

Особое место среди ценных достижений учёного в сфере теории сложности занимают две ключевые работы на темы теории вероятностно проверяемых доказательств и сложности аппроксимации . В 1988 году , на ежегодном, финансируемом Ассоциацией вычислительной техники (АВТ) , Михалис Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP (является подклассом Max-NP), содержащих ряд интересных задач оптимизации. Яннакакис и Пападимитриу показали, что эти задачи имеют некоторую ограниченную ошибку. С помощью этих выводов стало возможным объяснить замеченное в научно-исследовательском сообществе отсутствие прогресса в изучении аппроксимируемости целого ряда задач оптимизации, в том числе задачи « », задачи о независимом множестве , а также задачи коммивояжёра .

В 1993 году , на очередном симпозиуме АВТ по теории вычислений, Михалис Яннакакис и представили ряд важных выводов относительно вопросов вычислений аппроксимаций . Эти результаты показали трудность эффективного вычисления приближенных решений ряда задач минимизации, таких как случай раскраски графов и задача о покрытии множества . Учитывая маловероятность того, что такие будут разрешены оптимальным образом за полиномиальное время , было осуществлено много попыток разработать для них эффективные приближённые решения. Результаты, полученные Яннакакисом и Карстеном, доказали низкую вероятность достижения этой цели.

В области основной вклад Михалиса Яннакакиса состоит в инициировании исследований ациклических баз данных и недвухфазного блокирования. Ациклические схемы базы данных - это схемы, содержащие одну ациклическую зависимость соединения и набор функциональных зависимостей. Ряд исследователей, в том числе Яннакакис, отметили пригодность этих схем, продемонстрировав множество полезных свойств, которые они имеют: возможность решения многих задач, основанных на ациклических схемах за полиномиальное время, несмотря на то, что задача могла быть NP-полной для других схем.

Награды и премии

Удостоен Премии Кнута ( 2005 ) за значимость, влияние и поразительную степень его вклада в теоретические основы вычислительной техники, а также стал обладателем двух наград от Bell Labs: Distinguished Member of Technical Staff Award ( 1985 ) и President’s Gold Award ( 2000 ). Является членом Ассоциации вычислительной техники и исследовательского центра Лаборатории Белла .

Примечания

. NAS (1 мая 2018). Дата обращения: 3 мая 2018. 16 июня 2019 года.
от 7 марта 2016 на Wayback Machine (accessed 9 December 2009)
. 12 марта 2016 года.
Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, 2–4 May 1988.
Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, 16–18 May 1993.
Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, 11–13 May 1981.
Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983.