レスリー・ヴァリアント

レスリー・ヴァリアント フランス
2012年の勇敢な
生まれる	レスリー・ガブリエル・ヴァリアント ( 1949-03-28 )1949年3月28日（75歳） ブダペスト、ハンガリー共和国
国籍	イギリス
母校	ケンブリッジ大学（BA） インペリアル・カレッジ・ロンドン（MS） ウォーリック大学（博士号）
知られている	ヴァリアント・ヴァジラニの定理[2] 計数問題[3] おそらくほぼ正しい学習
受賞歴	チューリング賞(2010) EATCS賞（2008年） 米国科学アカデミー会員（2001年） クヌース賞(1997) AAAIフェロー（1992） ネヴァンリンナ賞（1986年）
科学者としてのキャリア
フィールド	数学 理論計算機科学 計算学習理論 理論神経科学
機関	ハーバード大学 エディンバラ大学
論文	決定論的プッシュダウンオートマトン族の決定手順 (1974)
博士課程の指導教員	マイク・パターソン[1]
博士課程の学生	マーク・ジェラム マイケル・カーンズ ダン・ロス[1]
Webサイト	people.seas.harvard.edu/~valiant

レスリー・ガブリエル・ヴァリアント FRS ^{[4] [5]}（1949年3月28日生まれ）は、イギリス系アメリカ人^[6]のコンピュータ科学者、計算理論家である。^{[7] [8]}化学技術者の父と翻訳家の母のもとに生まれた。^[9]現在はハーバード大学のT.ジェファーソン・クーリッジ計算機科学・応用数学教授である。 [ ^{10] [11] [12] [13]}ヴァリアントは、 ACMによって理論計算機科学の英雄的人物であり、科学における最も深い未解決の問題のいくつかに取り組む勇気と創造性、特に「深さと幅の驚くべき組み合わせ」により模範的な人物であると評され、2010年にチューリング賞を受賞した。^[6]

ヴァリアントはケンブリッジ大学キングス・カレッジ[ ^{14] [6]、} ロンドン大学インペリアル・カレッジ^{[14] [6]}、ウォーリック大学で教育を受け、1974年にウォーリック大学でコンピュータサイエンスの博士号を取得した。 ^{[15] [1]}

ヴァリアントは理論計算機科学の研究で世界的に有名である。複雑性理論への多くの貢献の中でも、列挙問題と信頼性問題が扱いにくい理由を説明するために#P 完全性（「シャープ P 完全性」）の概念を導入した。彼はおそらくほぼ正しい、または PAC 学習モデルを考案し、これは計算学習理論の分野を導入し、機械学習の開発の理論的基礎となった。彼はまた、量子計算モデルに触発されたホログラフィック アルゴリズムの概念も導入した。コンピュータ システムでは、バルク同期並列処理モデルの導入で最もよく知られている。単一のコンピュータ アーキテクチャのフォン ノイマン モデルと同様に、BSP は並列および分散コンピューティング アーキテクチャの有力なモデルとなっている。最近の例としては、Google がMapReduce、MillWheel、^[16] Pregel ^[17]、Dataflowを介して大規模計算にこれを採用し、Facebook が1 兆を超えるエッジを処理できるグラフ分析システムを作成していることがあげられる。^{[18] [19]}また、明示的なBSPプログラミングや、BSPから派生した他の高性能並列プログラミングモデルを追加するオープンソースプロジェクトも活発に行われています。人気のある例としては、Hadoop、Spark、Giraph、Hama、Beam、Daskなどがあります。オートマトン理論における彼の初期の研究には、文脈自由構文解析のアルゴリズムが含まれており、これは現在でも漸近的に最速であることが知られています。彼はまた、記憶と学習の理解に焦点を当てた 計算神経科学にも取り組んでいます。

ヴァリアントの2013年の著書は「おそらくほぼ正しい：複雑な世界で学び繁栄するための自然のアルゴリズム」である。^[20]その中で彼は、進化生物学は進化が起こる速度を説明していないと主張し、例えば「ダーウィンの進化に関する一般的な図式が本質的に正しいという証拠は、生物学者の大多数にとって説得力がある。著者は十分な数の自然史博物館を訪れ、自分自身も納得している。しかし、これらすべては、現在の進化論が十分に説明可能であることを意味するものではない。現在の進化論は、進化が複雑なメカニズムを開発したり、変化する環境でそれらを維持したりする速度を説明することができない。」と書いている。

ヴァリアントは 1982 年にハーバード大学で教鞭をとり始め、現在はハーバード大学応用科学工学部の T. ジェファーソン クーリッジ コンピュータ サイエンスおよび応用数学教授を務めています。1982 年以前は、カーネギー メロン大学、リーズ大学、エディンバラ大学で教鞭をとっていました。

ヴァリアントは1986年にネヴァンリンナ賞、 1997年にクヌース賞、 2008年にEATCS賞、^[21] 2010年にチューリング賞を受賞した。 ^{[22] [23]}彼は1991年に王立協会（FRS）フェローに選出され、^[4] 1992年に人工知能推進協会（AAAI）フェローに、 ^[24] 2001年に米国科学アカデミーの会員となった。 ^[25]ヴァリアントの王立協会への推薦文には次のように記されている。

レスリー・ヴァリアントは、理論計算機科学の発展に決定的な貢献をしてきました。彼の研究は主に、計算機で問題を解くためのリソースコストを数学的に定量化することに関係しています。初期の研究 (1975 年) では、文脈自由言語を認識するための漸近的に最速のアルゴリズムを発見しました。同時に、彼は計算を分析するためのグラフの通信特性の使用を開拓しました。1977 年には、「シャープ P」(#P) 完全性の概念を定義し、計算の扱いやすさに従って計数または列挙の問題を分類する際の有用性を確立しました。最初の応用は、マッチングの計数 (行列パーマネント関数) でした。1984 年、レスリーは帰納的学習の定義を導入しました。これは、計算の実行可能性と、学習すべき論理ルールの非自明なクラスへの適用可能性を初めて調和させる定義です。この概念は後に「おそらくほぼ正しい学習」と呼ばれるようになり、機械学習の発展の理論的基礎となった。1989年、彼は並列計算の統一原理としてバルク同期計算の概念を定式化した。レスリーは1986年にネヴァンリンナ賞、2010年にチューリング賞を受賞した。^[26]

AMチューリング賞の表彰状には次のように記されている。

計算理論への変革的貢献に対して。これには、おそらく近似的に正しい（PAC）学習理論、列挙と代数計算の複雑性、並列および分散計算の理論が含まれます。^[6]

彼の二人の息子、グレゴリー・ヴァリアント^[27]とポール・ヴァリアント^[28]も理論計算機科学者である。^[8]

 この記事には、CC BY 4.0 ライセンスに基づいて利用可能なテキストが組み込まれています。