莱斯利·瓦利安特：计算学习理论与复杂性理论的先驱

莱斯利·加布里埃尔·瓦利安特（1949年3月28日出生）是英裔美国计算机科学家与计算理论家，现任哈佛大学T·杰斐逊·柯立芝计算机科学与应用数学讲席教授。他因对计算学习理论和复杂性理论的贡献而闻名，特别是提出了PAC（概率近似正确）学习模型，该模型对现代机器学习算法产生了深远影响。

早年生活与教育

瓦利安特出生于匈牙利，童年移居英国。他先后就读于剑桥大学国王学院数学系，并于1973年获伦敦帝国理工学院计算机科学文凭。1974年在华威大学迈克·佩特森教授指导下完成博士论文《确定性下推自动机族的决策过程》，获计算机科学博士学位。

其基础教育完成于英格兰，先后就读于泰恩茅斯高中及伦敦历史悠久的拉提默中学（该校创立于1624年，据MacTutor史料记载）。

职业生涯与研究

瓦利安特的学术生涯包括以下重要职位：卡内基梅隆大学助理教授（1973-1974）、利兹大学讲师（1974-1976）、爱丁堡大学讲师与高级讲师（1976-1982），以及哈佛大学教授（1982年至今）。其研究涵盖理论计算机科学多个领域，主要贡献包括：1979年提出#P完全性概念，为计数问题的复杂性分类奠定基础；1984年提出PAC学习模型；发展全息算法及整体同步并行计算模型（BSP），对并行计算系统设计产生重要影响。

奖项与荣誉

瓦利安特获得的重要荣誉包括：

• 1986年奈望林纳奖
• 1997年高德纳奖
• 2008年EATCS奖
• 2010年图灵奖（表彰其对计算理论的变革性贡献）

他于1991年当选英国皇家学会会士，2001年成为美国国家科学院院士。