Михалис Яннакакис ( греч . Μιχάλης Γιαννακάκης ; родился 13 сентября 1953 года в Афинах , Греция ) [1] — профессор компьютерных наук в Колумбийском университете . Он известен своими работами в области вычислительной сложности , баз данных и других смежных областях. В 2005 году он получил премию Дональда Э. Кнута. [2] [3]
Яннакакис родился в Афинах, Греция, в 1953 году и посещал среднюю школу Варвакейо для своего начального образования. Он окончил Национальный технический университет Афин в 1975 году, получив диплом по электротехнике, а затем получил докторскую степень по компьютерным наукам в Принстонском университете в 1979 году. [1] Его диссертация называлась «Сложность задач максимального подграфа». [4]
В 1978 году он присоединился к Bell Laboratories и занимал должность директора отдела исследований принципов вычислений с 1991 по 2001 год, после чего он покинул Bell Laboratories и присоединился к Avaya Laboratories. Там он занимал должность директора отдела исследований принципов вычислений до 2002 года. [1]
В 2002 году он присоединился к Стэнфордскому университету , где был профессором компьютерных наук, и покинул его в 2003 году, чтобы присоединиться к Колумбийскому университету в 2004 году, где он в настоящее время занимает должность профессора компьютерных наук имени Перси К. и Виды Л. В. Хадсона . [1]
С 1992 по 2003 год Яннакакис входил в состав редколлегии журнала SIAM Journal on Computing и был главным редактором с 1998 по 2003 год. Он также был членом редколлегии журнала Journal of the ACM с 1986 по 2000 год. [1] Другие членства в редколлегии включают Journal of Computer and System Sciences , Journal of Combinatori Optimization и Journal of Complexity . Он также входил в состав комитетов конференций и председательствовал на различных конференциях, таких как ACM Symposium on Principles of Database Systems и IEEE Symposium on Foundations of Computer Science . [1]
По состоянию на июнь 2020 года его публикации цитировались около 35 000 раз, а его индекс Хирша составляет 93. [5]
Яннакакис известен своим вкладом в информатику в области теории сложности вычислений , теории баз данных , компьютерной проверки и тестирования, а также теории алгоритмических графов .
Среди его вкладов в теорию сложности есть две статьи о теории PCP и о сложности аппроксимации . На ежегодном симпозиуме ACM по теории вычислений 1988 года Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP. Max-NP и Max-SNP (который является подклассом Max-NP) содержат ряд интересных задач оптимизации, и Яннакакис и Пападимитриу показали, что эти задачи имеют некоторую ограниченную ошибку. Эти выводы смогли объяснить отсутствие прогресса, которое наблюдалось в исследовательском сообществе в отношении аппроксимируемости ряда задач оптимизации, включая 3SAT , задачу о независимом множестве и задачу коммивояжера . [6]
Яннакакис и Карстен Лунд представили ряд результатов, касающихся сложности вычислительных приближений, на ежегодном симпозиуме ACM по теории вычислений 1993 года. Эти результаты продемонстрировали сложность эффективного вычисления приближенных решений для ряда задач минимизации, таких как раскраска графа и покрытие множеств . Учитывая маловероятный сценарий, что NP-трудные задачи, такие как раскраска графа и покрытие множеств, будут решены оптимально за полиномиальное время , было предпринято много попыток разработать для них эффективные приближенные решения; результаты, полученные Яннакакисом и Карстеном, доказали маловероятность достижения этой задачи. [7]
В области теории баз данных его вклад включает в себя начало изучения ациклических схем баз данных, ациклических конъюнктивных запросов и недвухфазной блокировки. Ациклические схемы баз данных — это схемы, которые содержат одну ациклическую зависимость соединения (зависимость соединения — это отношение, управляющее соединением таблиц базы данных) и набор функциональных зависимостей; [8] ряд исследователей, включая Яннакакиса, указали на полезность этих схем, продемонстрировав множество полезных свойств, которыми они обладали: например, способность решать многие проблемы, основанные на ациклических схемах, за полиномиальное время, тогда как для других схем эта проблема могла бы легко быть NP-полной. [9]
Что касается недвухфазной блокировки , Яннакакис продемонстрировал, как знание о структуре базы данных и формах различных транзакций, выполняемых в них, может быть использовано для установления того, является ли конкретная политика блокировки безопасной или нет. Обычно используемые политики двухфазной блокировки (2PL) состоят из двух этапов — для блокировки и разблокировки сущностей соответственно — и чтобы избежать такой политики, необходимо наложить некоторую структуру на сущности базы данных; результаты Яннакакиса показывают, как, выбрав гиперграф, напоминающий структуру ограничения согласованности базы данных, политика блокировки, которая посещает сущности по путям этого гиперграфа, будет безопасной. Такая политика не обязательно должна быть двухфазной, и эти политики можно классифицировать в соответствии со связностью вышеупомянутого гиперграфа, причем политики 2PL являются лишь одним из них. [10] Яннакакис продолжил показывать, что для естественного класса политик безопасной блокировки (L-политик) свобода от тупиков определяется исключительно порядком, в котором транзакции осуществляют доступ к сущностям, и из этого выведены простые условия, которые гарантируют свободу от тупиков для L-политики. [11]
Он также внес вклад в область компьютерной проверки и тестирования, где он заложил строгие алгоритмические и сложно-теоретические основы этой области. Некоторые из его вкладов включают проектирование эффективных по памяти алгоритмов для проверки временных свойств конечных программ, [12] определение сложности тестирования того, удовлетворяют ли программы своим спецификациям, выраженным в линейной временной логике , [13] и проверку того, что модель с временными ограничениями удовлетворяет заданному временному свойству. [14] Вместе с Алексом Гроусом и Дороном Пеледом он представил адаптивную проверку моделей, показав, что при наличии несоответствий между системой и соответствующей моделью результаты проверки могут быть использованы для улучшения модели. [15] Он также внес вклад в исследование диаграмм последовательности сообщений (MSC), где было показано, что слабая реализуемость неразрешима для ограниченных MSC-графов и что безопасная реализуемость находится в EXPSPACE , наряду с другими интересными результатами, связанными с проверкой MSC-графов. [16]
Яннакакис является членом Национальной инженерной академии и Национальной академии наук . Он был удостоен седьмой премии Кнута за вклад в теоретическую информатику. [3] Он также был награжден премией Bell Labs Distinguished Member of Technical Staff Award и золотой премией президента Bell Labs в 1985 и 2000 годах соответственно. Он является членом ACM, а также членом Bell Laboratories . [1] Он был избран членом Американской академии искусств и наук (AAAS) в 2020 году. [17]