レスリー・ヴァリアント

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

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

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

経歴

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