レスリー・ヴァリアント
Leslie Valiant (2005, photo from MFO)
生誕 (1949-03-28) 1949年3月28日（75歳）
国籍 イギリス
研究分野数学
計算機科学
研究機関ハーバード大学
出身校ケンブリッジ大学
インペリアル・カレッジ・ロンドン
ウォーリック大学
博士課程
指導教員Mike Paterson
主な業績ヴァリアント-ヴァジラーニの定理（英語版）
主な受賞歴チューリング賞 (2010)
EATCS Award (2008)
クヌース賞 (1997)
ネヴァンリンナ賞 (1986)
プロジェクト:人物伝
テンプレートを表示

レスリー・ガブリエル・ヴァリアント（Leslie Gabriel Valiant、1949年3月28日 - ）は、イギリスの計算機科学者で計算理論の専門家である[1]。

理論計算機科学での業績でよく知られている。計算複雑性理論において様々な貢献をしており、#P完全性の記法を導入して、なぜ数え上げ問題が難しいのかを説明した。また、機械学習の「確率的で近似的に正しい」（PAC、"probably approximately correct"）モデルを提唱して機械学習の理論的発展に貢献し、ホログラフィックアルゴリズム（英語版）の概念も提唱した。初期にはオートマタ理論を研究し、CYK法を発展させたヴァリアントのアルゴリズムを考案。これは2010年現在も、文脈自由文法を判定する漸近的に最速なアルゴリズムである。計算論的神経科学の分野でも記憶と学習についての研究を行っている。

特に有名な論文として Vijay Vazirani と共同執筆した論文があり、UNIQUE-SAT ∈ P ⇒ NP = RP を証明した（ヴァリアント-ヴァジラーニの定理（英語版））[2]。
経歴

ケンブリッジ大学キングス・カレッジ、インペリアル・カレッジ・ロンドンで学び、1974年にウォーリック大学で計算機科学の博士号を得た。1982年からハーバード大学で教職につき、2012年現在は同大学工学および応用科学部にて計算機科学と応用数学の教授を務めている。1982年以前には、カーネギーメロン大学、リーズ大学、エディンバラ大学で教えていた。
受賞歴

1986年 - ネヴァンリンナ賞

1997年 - クヌース賞

2008年 - EATCS Award[3]

2010年 - チューリング賞[4][5]

王立協会（1991年）、アメリカ人工知能学会のフェローであり、米国科学アカデミー会員である。
出典^ Hoffmann, L. (2011). “Q&A: Leslie Valiant discusses machine learning, parallel computing, and computational neuroscience”. Communications of the ACM 54 (6): 128. doi:10.1145/1953122.1953152. 
^ Valiant, L.; Vazirani, V. (1986). ⇒“NP is as easy as detecting unique solutions”. Theoretical Computer Science 47: 85?93. doi:10.1016/0304-3975(86)90135-0. ⇒http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf. 
^ David Peleg ⇒The EATCS Award 2008 - Laudatio for Professor Leslie Valiant European Association of Theoretical Computer Science.
^ Josh Fishman ⇒"‘Probably Approximately Correct’ Inventor, From Harvard U., Wins Turing Award" Chronicle of Higher Education March 9, 2011.
^ ⇒ACM Turing Award Goes to Innovator in Machine Learning ACM Computing News

外部リンク

レスリー・ヴァリアント - Mathematics Genealogy Project

⇒DBLP:Leslie G. Valiant publications in DBLP

表

話

編

歴
チューリング賞受賞者


アラン・パリス (1966)

モーリス・ウィルクス (1967)

リチャード・ハミング (1968)

マービン・ミンスキー (1969)

ジェームズ・H・ウィルキンソン (1970)

ジョン・マッカーシー (1971)

エドガー・ダイクストラ (1972)

チャールズ・バックマン (1973)

ドナルド・クヌース (1974)

アレン・ニューウェル / ハーバート・サイモン (1975)

マイケル・ラビン / デイナ・スコット (1976)

ジョン・バッカス (1977)

ロバート・フロイド (1978)

ケネス・アイバーソン (1979)

アントニー・ホーア (1980)

エドガー・F・コッド (1981)

スティーブン・クック (1982)

ケン・トンプソン / デニス・リッチー (1983)

ニクラウス・ヴィルト (1984)

リチャード・カープ (1985)

ジョン・ホップクロフト / ロバート・タージャン (1986)

ジョン・コック (1987)

アイバン・サザランド (1988)