レスリー・ヴァリアント

生誕 (1949-03-28) 1949年3月28日（77歳）

国籍 イギリス

研究分野 数学
計算機科学

研究機関 ハーバード大学

レスリー・ヴァリアント
Leslie Valiant (2005, photo from MFO)
生誕	(1949-03-28) 1949年3月28日（77歳）
国籍	イギリス
研究分野	数学 計算機科学
研究機関	ハーバード大学
出身校	ケンブリッジ大学 インペリアル・カレッジ・ロンドン ウォーリック大学
博士課程指導教員	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]。