ミハリス・ヤナカキス

1975年にアテネ国立工科大学から電気工学の学士号を取得したミハリス・ヤナカキス（Mihalis Yannakakis）は、計算複雑性理論における長いキャリアの幕を開けました。1953年にアテネで生まれ、後にプリンストン大学で計算機科学の博士号を取得し、その後データベース理論、検証、アルゴリズムグラフ理論に影響を与えました。

複雑性の基礎

ヤナカキスは2年以上にわたり産業研究に従事し、1978年にベル研究所で任期を開始しました。1991年から2001年まで、同所の計算原理研究部門のディレクターを務めました。この期間中の1988年にはクリストス・パパディミトリウと共同で複雑性クラスMax-NPおよびMax-SNPを定義し、巡回セールスマン問題や3SATなどのNP困難問題の近似における限界に厳密な説明を与えました。1993年のカーステン・ルンドとの研究では、グラフ彩色などの最小化問題に対する近似解の計算に伴う固有の困難さがさらに明確になりました。

データベースの革新

データベース理論への貢献は、非巡回スキーマの研究を通じたクエリ処理の最適化に焦点を当てていました。非巡回結合クエリに対するヤナカキス・アルゴリズムを導入し、これらの構造が多項式時間で解けることを示しました。クエリの最適化を超えて、データのハイパーグラフ構造とトランザクションの一貫性制約を利用してデッドロックを防ぎ、二相ロッキングの厳格な制約の外でもデータベースの安全性を維持できることを証明し、ロッキングポリシーを調査しました。

検証と学術的リーダーシップ

アカデミアに移行し、2002年にスタンフォード大学で教授職を務めた後、2004年にコロンビア大学に加わりました。現在はパーシー・K・アンド・ヴィダ・L・W・ハドソン記念計算機科学教授を務めています。コンピュータ支援検証に関する研究により、線形時間 temporal logic（線形時相論理）やメッセージ・シーケンス・チャートをテストするためのアルゴリズム的基礎が確立されました。また、アレックス・グロスおよびドロン・ペレドと共に、検証結果に基づいてシステムモデルを洗練させる手法である適応型モデル検査を開発しました。

無料テスト

あなたはどのくらい？

20問、8分の制限時間、そして受験者全員と比べたパーセンタイル。登録不要。

IQテストを受ける →

専門的評価

1998年から2003年まで『SIAM Journal on Computing』の編集長を務めるなど、編集分野において重要な存在感を維持してきました。その学術的地位は、全米科学アカデミー、全米工学アカデミー、アメリカ芸術科学アカデミー、ヨーロッパ・アカデミーの会員であることに反映されています。受賞歴には、2005年のクヌース賞や2023年のジョン・フォン・ノイマン理論賞が含まれます。