レスリー・ヴァリアント

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
レスリー・ヴァリアント
Leslie Valiant (2005, photo from MFO)
人物情報
生誕 1949年3月28日(65歳)
国籍 イギリスの旗 イギリス
出身校 ケンブリッジ大学
インペリアル・カレッジ・ロンドン
ウォーリック大学
学問
研究分野 数学
計算機科学
研究機関 ハーバード大学
博士課程
指導教員
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-SATPNP = RP を証明した(ヴァリアント-ヴァジラーニの定理英語版[2]

経歴[編集]

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

受賞歴[編集]

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

脚注[編集]

  1. ^ Hoffmann, L. (2011). “Q&A: Leslie Valiant discusses machine learning, parallel computing, and computational neuroscience”. Communications of the ACM 54 (6): 128. doi:10.1145/1953122.1953152. 
  2. ^ Valiant, L.; Vazirani, V. (1986). “NP is as easy as detecting unique solutions”. Theoretical Computer Science 47: 85–93. doi:10.1016/0304-3975(86)90135-0. http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf. 
  3. ^ David Peleg The EATCS Award 2008 - Laudatio for Professor Leslie Valiant European Association of Theoretical Computer Science.
  4. ^ Josh Fishman "‘Probably Approximately Correct’ Inventor, From Harvard U., Wins Turing Award" Chronicle of Higher Education March 9, 2011.
  5. ^ ACM Turing Award Goes to Innovator in Machine Learning ACM Computing News

外部リンク[編集]