レスリ??ヴァリアント
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年）、 アメリカ人工知能?? のフェロ?であり、 米?科?アカデミ? ?員である。

出典 [ 編集 ]

外部リンク [ 編集 ]

• レスリ??ヴァリアント - Mathematics Genealogy Project
• DBLP:Leslie G. Valiant publications in DBLP