Professor Leslie Valiant, born in 1949, Hungary, is a British computer scientist and computational theorist, currently acting as the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University

2010 Turing Award

Intro

Professor Leslie Valiant, born in 1949, Hungary, is a British computer scientist and computational theorist, currently acting as the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University

Education and Work Experience

- 1970, BA in Mathematics, King’s College, Cambridge, England
- 1974, PhD in Computer Science, University of WarwickFrom
- 1982, Gordon McKay Professor of Computer Science and Applied Mathematics, Harvard UniversityFrom
- 2001, T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics, Harvard University

Honors and Awards

- 1991, Fellow of the Royal Society
- 2001, member of the USA 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.

Biography