The 2010 Turing Award recognized Leslie Valiant for his transformative influence on theoretical computer science, a field he shaped through the development of fundamental models for learning and parallel processing. Born in Budapest in 1949, he has spent his career establishing the mathematical boundaries of what computers can achieve, bridging the gap between abstract logic and complex real-world computation.
Academic Foundations and Early Career
Valiant pursued his higher education at King's College, Cambridge, Imperial College London, and the University of Warwick, where he completed his PhD in 1974. His early teaching career included roles at Carnegie Mellon University from 1973 to 1974 and the University of Leeds between 1974 and 1976. He subsequently held a position at the University of Edinburgh from 1976 until 1982, before joining the faculty at Harvard University, where he currently serves as the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Contributions to Complexity Theory
His research in computational complexity led to the introduction of #P-completeness, a framework designed to explain why specific enumeration and reliability problems are inherently difficult to solve. This work allowed researchers to classify counting problems based on their computational tractability. Additionally, he developed an algorithm for context-free parsing that remains the fastest known approach in asymptotic terms.
Learning Models and Parallel Systems
Valiant created the Probably Approximately Correct (PAC) model, which provided a theoretical foundation for machine learning by defining the feasibility of inductive learning. In the realm of system architecture, he introduced the Bulk Synchronous Parallel (BSP) model. This framework offers a structure for parallel and distributed computing, analogous to the von Neumann model, and has been adopted by systems including MapReduce, Pregel, and various open-source projects like Hadoop and Spark.
Honors and Professional Appointments
A citizen of both the United Kingdom and the United States, Valiant is an elected member of the National Academy of Sciences, the Royal Society, and the American Academy of Arts and Sciences. Beyond his Turing Award, his career has been marked by the Nevanlinna Prize in 1986, the Knuth Prize in 1997, and the EATCS Award in 2008. He is also a fellow of the Association for the Advancement of Artificial Intelligence.
Fast facts
- Born: 1949, Budapest
- Current Position: Professor at Harvard University
- Primary Fields: Computer Science, Mathematics
- Education: University of Warwick, Imperial College London, King's College
- Notable Recognition: Turing Award (2010)
- Citizenship: United Kingdom, United States
Questions readers ask
What is the primary contribution of the PAC model?
It introduced a theoretical basis for machine learning by reconciling computational feasibility with the logical rules to be learned.
Why is the BSP model significant?
It serves as an influential model for parallel and distributed computing architectures, enabling large-scale data processing.
Achievements
- Turing Award — 2010
- Affiliated with Harvard University, University of Leeds and University of Edinburgh
- Educated at Imperial College London, University of Warwick and King's College
- Worked as computer scientist, university teacher and mathematician
