A longer and more detailed reasoning explains that
over the past 30 years, Leslie Valiant (right) has made fundamental contributions to many aspects of theoretical computer science, opening new frontiers, introducing ingenious new concepts and presenting results of great originality, depth, and beauty.

Time and again, his work has literally defined or transformed the computer science research landscape.
Valiant's greatest single contribution may be his 1984 paper "A Theory of the Learnable," which laid the foundations of computational learning theory.

He introduced a general framework as well as concrete computational models for studying the learning process, including the famous "probably approximately correct" (PAC) model of machine learning.

This has developed into a vibrant research area and has had enormous influence on machine learning, artificial intelligence, and many areas of computing practice, such as natural language processing, handwriting recognition, and computer vision.

Valiant has also made many seminal contributions to computational complexity.  He introduced the notion of complexity of enumeration, in terms of the complexity class ##P. The most surprising consequence of this was that natural enumeration problems can be intractable even when the corresponding decision problem is tractable.

Another fundamental contribution to computational complexity was his theory of algebraic computation, in which he established a framework for understanding which algebraic formulas can be evaluated efficiently. In analogy with the Boolean complexity classes P and NP, his theory characterizes the difficulty of computing fundamental functions in linear algebra, namely the determinant and permanent.

Together with his work on ##P, this set the stage for some of the most exciting subsequent developments in computational complexity, such as the development of interactive proofs for problems beyond NP.

A third broad area in which Valiant has made important contributions is the theory of parallel and distributed computing. His design of randomised routing strategies laid the groundwork for a rich body of research that exposed how randomisation can be used to offset congestion effects in communication networks.

He proposed the bulk synchronous model of parallel computation. He also posed a number of influential challenges leading to the construction of parallel algorithms for seemingly inherently sequential problems.

Finally, the superconcentrators constructed by Valiant in the context of computational complexity established the fundamental role of expander graphs in computation.

Leslie G. Valiant in CV
Valiant is the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University's School of Engineering and Applied Sciences (SEAS). Before joining Harvard in 1982, he taught at Carnegie Mellon University, Leeds University, and the University of Edinburgh.

He is a graduate of Kings College, University of Cambridge, with a BA in Mathematics, and Imperial College London, where he received a Diploma of the Imperial College (DIC) in Computer Science. He earned a Ph.D. in Computer Science from the University of Warwick.

A recipient of the Nevanlinna Prize from the International Mathematical Union in 1986, Valiant was awarded the 1997 Knuth Prize from the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing.

In 2008, he received the European Association for Theoretical Computer Science Award. He is a Fellow of the Royal Society (London), a Fellow of the American Association for Artificial Intelligence, and a member of the National Academy of Sciences (USA).