レスリー・ヴァリアント
レスリー・ガブリエル・ヴァリアント(Leslie Gabriel Valiant、1949年3月28日 - )は、イギリスの計算機科学者で計算理論の専門家である。
理論計算機科学での業績でよく知られている。計算複雑性理論において様々な貢献をしており、#P完全性の記法を導入して、なぜ数え上げ問題が難しいのかを説明した。また、機械学習の「確率的で近似的に正しい」(PAC、"probably approximately correct")モデルを提唱して機械学習の理論的発展に貢献し、ホログラフィックアルゴリズム(英語版)の概念も提唱した。初期にはオートマタ理論を研究し、CYK法を発展させたヴァリアントのアルゴリズムを考案。これは2010年現在も、文脈自由文法を判定する漸近的に最速なアルゴリズムである。計算論的神経科学の分野でも記憶と学習についての研究を行っている。
特に有名な論文として Vijay Vazirani と共同執筆した論文があり、UNIQUE-SAT ∈ P ⇒ NP = RP を証明した(ヴァリアント-ヴァジラーニの定理(英語版))。