莱斯利·加布里埃尔·瓦利安特（Leslie Gabriel Valiant，1949年3月28日出生）是一位英美计算机科学家和计算理论家，现任哈佛大学计算机科学与应用数学T. Jefferson Coolidge教授。他最著名的是提出了概率近似正确（PAC）学习模型，该模型奠定了计算学习理论领域的基础，并成为机器学习的理论基础。他还在复杂性理论中引入了#P完全性概念，并为并行计算提出了批量同步并行（BSP）模型。美国计算机协会授予他2010年图灵奖，称他为理论计算机科学领域的“英雄人物”，赞扬他在解决科学中深层未解问题方面“兼具深度与广度的惊人结合”。
瓦利安特出生于一个化学工程师父亲和翻译母亲的家庭。他在剑桥大学国王学院、伦敦帝国理工学院和华威大学接受高等教育，并于1974年在华威大学获得计算机科学博士学位。在1982年加入哈佛大学之前，他曾在爱丁堡大学、利兹大学和卡内基梅隆大学担任学术职务。
复杂性理论与#P完全性
1977年，瓦利安特引入了复杂性类#P（Sharp-P），用于对计数和枚举问题进行分类，例如计算矩阵的积和式或计算图中的匹配数。他的工作将#P完全性确立为复杂性理论中的一个基本概念，解释了为什么许多可靠性和枚举问题在计算上是难解的，尽管它们是易于验证的判定问题。这一贡献重塑了理论家对超越简单任务的问题难度的理解。
PAC学习与计算学习理论
1984年，瓦利安特定义了一个归纳学习框架，该框架将计算可行性与非平凡逻辑规则类的适用性相结合。这个后来被称为概率近似正确（PAC）学习的框架，形式化了学习者如何从有限数量的样本中进行泛化，同时容忍较小的错误概率。PAC学习为机器学习提供了理论基础，解决了样本复杂性和计算可处理性等问题。他在2013年出版的著作《Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World》中扩展了这些思想，认为学习不仅支撑计算，还支撑进化和认知。在书中，他认为进化生物学缺乏对进化速率及其在变化环境中发展复杂机制能力的充分解释，尽管达尔文图式的整体正确性毋庸置疑。
教育与早期生涯
瓦利安特曾在剑桥大学国王学院和伦敦帝国理工学院学习，之后于1974年在华威大学完成计算机科学博士学位。他在自动机理论方面的早期工作产生了一种上下文无关解析算法，该算法至今仍是渐近意义下最快的算法。他还率先利用图的性质来分析计算，将图论与算法效率联系起来。
对计算的贡献
瓦利安特的研究跨越理论计算机科学的多个领域。他引入了#P完全性概念来解释为什么可靠性和枚举问题难以处理，其首个应用是矩阵积和式。1984年，他提出了PAC学习模型，该模型为从示例中学习提供了严格的定义，并成为人工智能的基础。他还发展了全息算法，受到量子计算的启发，并在自动机理论方面做出了早期贡献，提出了一种上下文无关解析算法，该算法至今仍是渐近意义下最快的算法。在20世纪90年代，瓦利安特提出了批量同步并行（BSP）模型，该模型类似于冯·诺依曼模型，但面向并行架构；它影响了诸如谷歌的Pregel和Beam等系统，以及Hadoop和Spark等开源项目。
教育与学术生涯
瓦利安特曾在剑桥大学国王学院学习，之后在伦敦帝国理工学院学习，并于1974年在华威大学获得计算机科学博士学位。他先后在爱丁堡大学和卡内基梅隆大学任教，之后于1982年加入哈佛大学，并一直工作至今。在哈佛大学，他从事理论计算机科学和计算神经科学研究，专注于理解记忆和学习过程。
PAC学习与机器学习
瓦利安特于1984年引入的PAC模型形式化了学习者从有限示例集合中进行泛化的条件。该框架将计算可行性与逻辑规则类学习相结合，成为计算学习理论的基石，并影响了实用人工智能系统的发展。他在2013年出版的著作《Probably Approximately Correct》中将这些思想扩展到生物学和进化领域，认为当前的进化理论不能充分解释进化进展的速度，而学习理论提供了有用的类比。
并行与分布式计算
瓦利安特于1990年提出的批量同步并行（BSP）模型为并行计算提供了硬件与软件之间的桥梁，通过将执行组织为带有屏障同步的超步来实现。该模型影响了分布式处理系统，如谷歌的Pregel以及开源项目Apache Giraph、Apache Hama、Apache Beam和Dask。他在施乐帕洛阿尔托研究中心的早期工作以及后来的学术研究为现代数据中心使用的可扩展图分析引擎奠定了基础。
奖项与荣誉
瓦利安特于1986年获得内万林纳奖，1997年获得克努斯奖，2008年获得EATCS奖，2010年获得A.M.图灵奖。他于1997年当选为英国皇家学会会士，并成为美国国家科学院院士。他的图灵奖表彰了他在PAC学习理论、枚举和代数计算复杂性以及并行和分布式计算理论方面的变革性贡献。
个人生活
瓦利安特已婚，有两个儿子，格雷戈里·瓦利安特和保罗·瓦利安特，两人都是计算机科学家。格雷戈里在斯坦福大学从事算法和概率研究，保罗从事计算复杂性和密码学研究。瓦利安特一家致力于理论计算机科学，两个儿子都在各自的领域做出了贡献。