Leslie Valiant
  • 2010 Turing Award


2010 Turing Award
A heroic figure in theoretical computer science. He was awarded the Turing Award in 2010 for “transformative contributions to the theory of computation, including the theory of probably
approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing”

Education and Work Experience

1974, Ph.D. in Computer Science, University of Warwick
1982, Gordon McKay Professor of Computer Science and Applied Mathematics, Harvard University
From 2001, T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics, Harvard University

Honors and Awards

1991, Fellow of Royal Society
2001, Member of the United States National Academy of Sciences
2008, European Association for Theoretical Computer Science Distinguished Achievement Award
2010, Turing Award

Major Academic Achievements

Valiant is world-renowned for his work in theoretical computer science. Among his many contributions to complexity theory he introduced the notion of #P-completeness to explain why enumeration and reliability problems are intractable. He also introduced the "probably approximately correct" PAC model of machine learning that has helped the field of computational learning theory grow and the concept of holographic algorithms. In computer systems he is most well-known for introducing the bulk synchronous parallel processing model. His earlier work in automata theory includes an algorithm for context-free parsing which is as of 2010 still the asymptotically fastest known. He also works in computational neuroscience focusing on understanding memory and learning.