Loading article…
ミハリス・ヤナカキス（ギリシャ語: Μιχάλης Γιαννακάκης 、1953年9月13日ギリシャのアテネ生まれ）[ 1 ]は、コロンビア大学のコンピュータサイエンスの教授です。彼は計算複雑性、データベース、その他の関連分野での研究で知られています。彼は2005年にドナルド・E・クヌース賞を受賞しました。 [ 2 ] [ 3 ]
ヤナカキスは1953年にギリシャのアテネで生まれ、初等教育はヴァルヴァケイオ高校で受けた。1975年にアテネ国立工科大学を電気工学の学位を取得して卒業し、 1979年にプリンストン大学でコンピュータサイエンスの博士号を取得した。 [ 1 ]彼の博士論文のタイトルは「最大部分グラフ問題の複雑性」であった。[ 4 ]
1978年にベル研究所に入社し、1991年から2001年までコンピューティング原理研究部門のディレクターを務め、その後ベル研究所を退社してアバヤ研究所に入社した。アバヤ研究所では2002年までコンピューティング原理研究部門のディレクターを務めた。[ 1 ]
2002年にスタンフォード大学に着任し、コンピュータサイエンスの教授を務めた後、2003年に退任し、2004年にコロンビア大学に移籍。現在はパーシー・K・ハドソンおよびヴィダ・L・W・ハドソン記念コンピュータサイエンス教授を務めている。[ 1 ]
1992年から2003年まで、ヤナカキスはSIAM Journal on Computingの編集委員を務め、 1998年から2003年までは編集長を務めた。また、 1986年から2000年まではJournal of the ACMの編集委員も務めた。[ 1 ]その他、Journal of Computer and System Sciences、Journal of Combinatorial Optimization、Journal of Complexityの編集委員も務めた。また、 ACM Symposium on Principles of Database SystemsやIEEE Symposium on Foundations of Computer Scienceなど、さまざまな会議の委員会委員や議長も務めた。[ 1 ]
ヤナカキスは、計算複雑性理論、データベース理論、コンピュータ支援検証およびテスト、アルゴリズムグラフ理論といった分野におけるコンピュータ科学への貢献で知られている。
複雑性理論への彼の貢献の中には、PCP理論と近似の困難性に関する2つの論文がある。 1988年のACM理論計算シンポジウムで、ヤナカキスとクリストス・パパディミトリウは複雑性クラスMax-NPとMax-SNPの定義を紹介した。Max-NPとMax-SNP（Max-NPのサブクラス）には多くの興味深い最適化問題が含まれており、ヤナカキスとパパディミトリウはこれらの問題にはある程度の誤差があることを示した。これらの発見は、3SAT 、独立集合問題、巡回セールスマン問題など、多くの最適化問題の近似可能性に関する研究コミュニティで見られた進歩の欠如を説明することができた。[ 6 ]
ヤナカキスとカーステン・ルンドは、 1993年のACM理論計算シンポジウムで、近似計算の難しさに関するいくつかの発見を発表しました。これらの発見は、グラフ彩色や集合被覆などの多くの最小化問題に対する近似解を効率的に計算することの難しさを示しました。グラフ彩色や集合被覆などのNP困難問題が多項式時間で最適に解かれる可能性は低いことから、これらの問題に対する効率的な近似解を開発する試みが数多く行われてきました。ヤナカキスとカーステンが得た結果は、この課題を達成する可能性が低いことを証明しました。[ 7 ]
データベース理論の分野では、彼の貢献には、非巡回データベーススキーム、非巡回結合クエリ（ヤナカキスアルゴリズム）、および非2相ロックの研究の開始が含まれます。非巡回データベーススキームは、単一の非巡回結合依存関係（結合依存関係は、データベースのテーブルの結合を規定する関係）と関数依存関係の集合を含むスキームです。[ 8 ]ヤナカキスを含む多くの研究者は、これらのスキームが持つ多くの有用な特性を示すことによって、これらのスキームの有用性を指摘しました。たとえば、他のスキームでは容易にNP完全となる問題に対して、非巡回スキームに基づく多くの問題を多項式時間で解決できる能力などです。[ 9 ]
2 相ロック以外のロックに関して、Yannakakis は、データベースの構造と、その上で実行されるさまざまなトランザクションの形式に関する知識を使用して、特定のロック ポリシーが安全かどうかを判断できることを示しました。一般的に使用される 2 相ロック (2PL) ポリシーは、エンティティをロックおよびロック解除するための 2 つのステージで構成されており、このようなポリシーを回避するには、データベースのエンティティに何らかの構造を課す必要があります。Yannakakis の結果は、データベースの一貫性制約構造に似たハイパーグラフを選択することで、このハイパーグラフのパスに沿ってエンティティを訪れるロック ポリシーが安全になることを示しています。このようなポリシーは 2 相である必要はなく、これらのポリシーは、前述のハイパーグラフの接続性に応じて分類でき、2PL ポリシーはこれらの特定の例の 1 つにすぎません。[ 10 ]ヤナカキスは、安全なロックポリシーの自然なクラス（Lポリシー）の場合、デッドロックからの解放はトランザクションによってエンティティにアクセスする順序のみによって決定されることを示し、このことからLポリシーのデッドロックからの解放を保証する単純な条件を導き出した。[ 11 ]
彼はまた、コンピュータ支援検証およびテストの分野にも貢献しており、この分野の厳密なアルゴリズム的および複雑性理論的な基礎を築きました。彼の貢献には、有限状態プログラムの時間的特性の検証のためのメモリ効率の良いアルゴリズムの設計[ 12 ] 、線形時間時相論理で表現された仕様を満たすプログラムのテストの複雑性の決定[ 13 ]、タイミング制約のあるモデルが与えられた時間的特性を満たすことの検証[ 14 ]などがあります。アレックス・グロースとドロン・ペレドとともに、彼は適応型モデル検査を導入し、システムと対応するモデルの間に矛盾がある場合、検証の結果を使用してモデルを改善できることを示しました。[ 15 ]彼はまた、メッセージシーケンスチャート(MSC) の研究にも貢献しており、MSC グラフの検証に関連するその他の興味深い結果とともに、弱実現可能性が有界 MSC グラフでは決定不能であり、安全実現可能性がEXPSPACEに含まれることが示されています。[ 16 ]
ヤナカキスは、複雑性クラスFIXPの発明者の一人である。
ヤナカキスは、米国工学アカデミーと米国科学アカデミーの両方の会員です。理論計算機科学への貢献により、第7回クヌース賞を受賞しました。 [ 3 ]また、1985年にベル研究所優秀技術スタッフ賞、2000年にベル研究所所長金賞も受賞しています。ACMのフェローであり、ベル研究所のフェローでもあります。 [ 1 ] 2020年には、米国芸術科学アカデミー（AAAS）のフェローに選出されました。[ 17 ]