レスリー・ヴァリアント

レスリー・ガブリエル・ヴァリアント（、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 Award
 2010年 - チューリング賞

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

出典

外部リンク 
 
 DBLP:Leslie G. Valiant publications in DBLP

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