Leslie Gabriel Valiant (born 28 March 1949) is a British American computer scientist and computational theorist, currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. He is best known for introducing the Probably Approximately Correct (PAC) model of learning, which founded the field of computational learning theory and became a theoretical basis for machine learning. He also introduced the #P-completeness concept in complexity theory and the Bulk Synchronous Parallel (BSP) model for parallel computing. The Association for Computing Machinery awarded him the 2010 A.M. Turing Award, describing him as a "heroic figure" in theoretical computer science for his "striking combination of depth and breadth" in addressing deep unsolved problems in science.
Valiant was born to a chemical engineer father and a translator mother. He pursued higher education at King's College, Cambridge, Imperial College London, and the University of Warwick, where he earned a PhD in computer science in 1974. Before joining Harvard in 1982, he held academic positions at the University of Edinburgh, the University of Leeds, and Carnegie Mellon University.
Complexity Theory and #P-Completeness
In 1977, Valiant introduced the complexity class #P (Sharp-P) to classify counting and enumeration problems, such as computing the permanent of a matrix or counting matchings in a graph. His work established #P-completeness as a fundamental notion in complexity theory, explaining why many reliability and enumeration problems are computationally intractable despite being decision problems that are easy to verify. This contribution reshaped how theorists understand the difficulty of problems beyond simple decision tasks.
PAC Learning and Computational Learning Theory
In 1984, Valiant defined a framework for inductive learning that combined computational feasibility with applicability to nontrivial logical rule classes. This framework, later called Probably Approximately Correct (PAC) learning, formalized how a learner can generalize from a limited number of samples while tolerating a small probability of error. PAC learning provided a theoretical basis for machine learning, addressing questions about sample complexity and computational tractability. His 2013 book Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World extended these ideas, arguing that learning algorithms underpin not just computing but also evolution and cognition. In the book, he contended that evolutionary biology lacks an adequate account of evolution's rate and its ability to develop complex mechanisms under changing environments, despite the overall correctness of Darwin's schema.
Education and early career
Valiant studied at King's College, Cambridge, and Imperial College London before completing a PhD in computer science at the University of Warwick in 1974. His early work in automata theory produced an algorithm for context-free parsing that remains the asymptotically fastest known. He also pioneered the use of graph properties for analyzing computations, linking structural graph theory to algorithmic efficiency.
Contributions to computation
Valiant's research spans multiple areas of theoretical computer science. He introduced the notion of #P-completeness to explain why enumeration and reliability problems are intractable, with the first application being the matrix permanent function. In 1984 he proposed the PAC learning model, which provided a rigorous definition of learning from examples and became foundational for artificial intelligence. He also developed holographic algorithms, inspired by quantum computation, and made early contributions to automata theory with a context-free parsing algorithm that remains the asymptotically fastest known. In the 1990s, Valiant formulated the Bulk Synchronous Parallel (BSP) model, analogous to the von Neumann model but for parallel architectures; it has influenced systems such as Google's Pregel and Beam, and open-source projects like Hadoop and Spark.
Education and academic career
Valiant studied at King's College, Cambridge, then at Imperial College London, and received his PhD in computer science from the University of Warwick in 1974. He taught at the University of Edinburgh and then Carnegie Mellon University before joining Harvard University in 1982, where he has remained since. At Harvard, he has worked in theoretical computer science and computational neuroscience, focusing on understanding memory and learning processes.
PAC Learning and Machine Learning
Valiant's 1984 introduction of the PAC model formalized the conditions under which a learner can generalize from a finite set of examples. This framework reconciled computational feasibility with learning logical rulesainer - it became a cornerstone of computational learning theory and influenced the development of practical artificial intelligence systems. His 2013 book Probably Approximately Correct extended these ideas to biology and evolution, arguing that current evolutionary theory does not adequately explain the rate of evolutionary progress and that learning theory offers useful analogies.
Parallel and Distributed Computing
Valiant's Bulk Synchronous Parallel model, introduced in 1990, provides a bridge between hardware and software for parallel computation by organizing execution into supersteps with barrier synchronization. The model influenced distributed processing systems such as Google's Pregel and the open-source projects Apache Giraph, Apache Hama, Apache Beam, and Dask. His earlier work at Xerox PARC-adjacent contexts and later academic research laid groundwork for scalable graph analytics engines used in modern data centers.
Awards and Honors
Valiant received the Nevanlinna Prize in 1986, the Knuth Prize in 1997, the EATCS Award in 2008, and the A.M. Turing Award in 2010. He was elected a Fellow of the Royal Society (FRS) in 1997 and a member of the United States National Academy of Sciences. His Turing Award citation recognized his transformative contributions to the theory of PAC learning, the complexity of enumeration and algebraic computation, and the theory of parallel and distributed computing.
Personal life
Valiant is married and has two sons, Gregory Valiant and Paul Valiant, both of whom are computer scientists. Gregory works on algorithms and statistics at Stanford University, and Paul works on computational complexity and cryptography. Valiant's family shares his dedication to theoretical computer science, with both sons contributing to the field in their own research.