レスリー・ヴァリアント

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

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

特に有名な論文として Vijay Vazirani と共同執筆した論文があり、UNIQUE-SAT ∈ P ⇒ NP = RP を証明した（）。

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

 受賞歴 
 1986年 - ネヴァンリンナ賞
 1997年 - クヌース賞
 2008年 - EATCS AwardDavid Peleg The EATCS Award 2008 - Laudatio for Professor Leslie Valiant European Association of Theoretical Computer Science.
 2010年 - チューリング賞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

王立協会（1991年）、アメリカ人工知能学会のフェローであり、米国科学アカデミー会員である。

 出典 


 外部リンク 

 DBLP:Leslie G. Valiant publications in DBLP

Category:イギリスの計算機科学者
Category:理論計算機科学者
Category:オライリー・オープン・ソース賞の受賞者
Category:ネヴァンリンナ賞の受賞者
Category:クヌース賞の受賞者
Category:チューリング賞受賞者
Category:ハーバード大学の教員
Category:米国科学アカデミー会員
Category:王立協会フェロー
Category:ACMフェロー
Category:ヨーロッパ・アカデミー会員
Category:アメリカ科学振興協会フェロー
Category:アメリカ人工知能学会フェロー
Category:アメリカ芸術科学アカデミー会員
Category:マサチューセッツ州ミドルセックス郡出身の人物
Category:ウォーリック大学出身の人物
Category:ケンブリッジ大学キングス・カレッジ出身の人物
Category:インペリアル・カレッジ・ロンドン出身の人物
Category:1949年生
Category:存命人物