The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Leslie G. Valiant

Born 28 March 1949, Budapest, Hungary

Turing Award (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”.

Nevanlinna Prize (1986) “for contributing in a decisive way to the growth of many branches of computer science: solving the recognition problem of context-free grammars in cubic time; proving that superconcentrators of linear size exist; discovering complete counting problems that correspond to easy search problems, thereby considerably enlarging the scope of the theory of NP-completeness”.

Leslie Valiant’s father, also Leslie, was a chemical engineer, and his mother Eva a multilingual translator. He received his education in Britain. He studied Mathematics at King’s College, Cambridge (Bachelor of Arts, 1970) and Computer Science at Imperial College in London (Diploma of Imperial College). He did his Ph.D. (1971-73) at the University of Warwick, advised by Michael Paterson, with a thesis on “Decision Procedures for Families of Deterministic Pushdown Automata”. He then worked for a year as a Visiting Assistant Professor at Carnegie Mellon University in Pittsburgh, Pennsylvania (1973-1974). Subsequently, he worked as a lecturer at Leeds University (1974-1976), and lecturer and reader at the University of Edinburgh (1977-1982). In 1982, he went to Harvard University where he became Gordon McKay Professor for Computer Science and Applied Mathematics, and in 2001 T. Jefferson Coolidge Professor for Computer Science and Applied Mathematics. He received the Knuth Prize in 1997 and the European Association for Theoretical Computer Science Award in 2008.

Graphs are mathematical objects which can be likened to street maps. Vertices (cities) are connected by edges (roads). Roads can go over or under each other. On a graph, one can play a game: the task is to select some roads so that for each city no more than a single road in the selection starts or ends there. Such a selection is called a matching. If there is exactly one selected street leading to each city then the matching is called perfect. Given a graph the two most natural questions one can ask about matchings are whether there exists a perfect matching in the graph, and, if so, how many. In the 1970s, Leslie Valiant studied problems of the second kind, namely those where one wants to count the number of solutions to a given problem. Valiant showed the amazing fact that while determining the existence of a matching is easy, counting their number is computationally much more difficult (#P-complete) and possibly intractable in practice for large graphs. Further, he demonstrated that this dichotomy between the ease of determining existence of solutions, and the difficulty of counting them is a pervasive phenomenon to be found throughout mathematics and computing.

Leslie Valiant is also famous for laying the foundations of the theory of learning, in a paper “A theory of the learnable” published in 1984. This field addresses the age-old problem of how, from seeing examples classified according to various categories, such as flowers categorized according to species, one can derive a generalization that is effective in correctly categorizing examples not previously seen. The paper provides a mathematical criterion, called the “probably approximately correct” criterion, for when such a process of learning can be considered to be successful and computationally feasible. This basic definition of learning relates directly to the technology of machine learning. Valiant has also adapted it to provide a mathematical theory of the scope and limits of biological evolution.

Leslie married Gayle Dyckoff, a psychologist, in 1977. They have two sons, Paul and Gregory.