Михалис Яннакакис

Диплом в области электротехники, который Михалис Яннакакис (Mihalis Yannakakis) получил в Национальном техническом университете Афин в 1975 году, ознаменовал начало долгой карьеры в теории вычислительной сложности. Родившись в 1953 году в Афинах, он позже получил степень доктора философии по информатике в Принстонском университете, после чего оказал влияние на теорию баз данных, верификацию и алгоритмическую теорию графов.

Основы теории сложности

Яннакакис провел более двух десятилетий в индустриальных исследованиях, начав работу в Bell Laboratories в 1978 году. С 1991 по 2001 год он занимал там должность директора Отдела исследований принципов вычислений. В этот период он сотрудничал с Христосом Пападимитриу в 1988 году для определения классов сложности Max-NP и Max-SNP, предоставив строгое объяснение ограничений, наблюдаемых при приближенном решении NP-трудных задач, таких как задача коммивояжера и 3SAT. Его работа 1993 года с Карстеном Лундом дополнительно прояснила присущую трудность вычисления приближенных решений для задач минимизации, таких как раскраска графов.

Инновации в базах данных

Его вклад в теорию баз данных был сосредоточен на оптимизации обработки запросов посредством изучения ациклических схем. Он представил алгоритм Яннакакиса для ациклических конъюнктивных запросов, продемонстрировав, что эти структуры могут быть решены за полиномиальное время. Помимо оптимизации запросов, он исследовал политики блокировок, доказав, что безопасность баз данных может поддерживаться за пределами жестких ограничений двухфазной блокировки путем использования гиперграфовой структуры данных и ограничений согласованности транзакций для предотвращения взаимных блокировок.

Верификация и академическое лидерство

Перейдя в академическую среду, Яннакакис занимал профессорскую должность в Стэнфордском университете в 2002 году, прежде чем перейти в Колумбийский университет в 2004 году. В настоящее время он является профессором информатики имени Перси К. и Виды Л. В. Хадсон. Его исследования в области компьютерной верификации заложили алгоритмические основы для тестирования линейной темпоральной логики и диаграмм последовательности сообщений. Он также разработал адаптивную проверку моделей вместе с Алексом Гроусом и Дороном Пеледом — метод, который уточняет системные модели на основе результатов верификации.

Профессиональное признание

Яннакакис внес значительный вклад в издательскую деятельность, занимая пост главного редактора SIAM Journal on Computing в период с 1998 по 2003 год. Его академический статус отражен в его членстве в Национальной академии наук, Национальной академии инженерных наук, Американской академии искусств и наук и Academia Europaea. Среди его наград — премия Кнута 2005 года и премия по теории Джона фон Неймана 2023 года.

Краткие факты

- Рождение: 1953, Афины, Греция - Доктор философии (PhD): Принстонский университет, 1979 - Премия Кнута: 2005 - Премия по теории Джона фон Неймана: 2023 - Феллоу ACM: 1998 - Гражданство: США; Греция - Языки: новогреческий

Вопросы читателей

### Что такое алгоритм Яннакакиса?

Это метод, используемый для выполнения ациклических конъюнктивных запросов в системах баз данных, позволяющий решать их за полиномиальное время.

### С какими учреждениями был связан Яннакакис?

Он работал в Bell Laboratories, Avaya Laboratories, Стэнфордском университете и Колумбийском университете.