Born: 28 March 1949 in Budapest, Hungary

Leslie Valiant's parents were Leslie Valiant and Eva Julia Ujlaki. He was brought up in England, attending Tynemouth High School, North Shields. This school was renamed in 1969, several years after Valiant left, when it became known as Norham High School. Valiant completed his school education at Latymer Upper School, in King Street, Hammersmith, London. This was (and still is) a famous selective independent school with a great reputation dating back to its founding by Edward Latymer in 1624. After graduating from Latymer Upper School, he studied at King's College, Cambridge then, after the award of his first degree, a BA in mathematics, he entered Imperial College, London to study theoretical computer science. After the award of the Diploma of the Imperial College in Computer Science, Valiant went to the University of Warwick where he undertook research for a doctorate in computer science with Michael Stewart Paterson as his advisor.

Before the award of his Ph.D., Valiant spent the year 1973-74 in the United States as a Visiting Assistant professor at Carnegie Mellon University in Pittsburgh, Pennsylvania. He was awarded his doctorate by the University of Warwick in 1974 for his thesis Decision Procedures for Families of Deterministic Pushdown Automata. In collaboration with his thesis advisor M S Paterson, Valiant had presented the paper Deterministic one-counter automata to the Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen in Bonn in 1973. Wilfried Brauer reviewed the paper, writing:-

A deterministic one-counter automaton (doca) is a deterministic pushdown automaton having a one-element stack alphabet. It is easy to see that the inclusion and the nullity-of-intersection problems for doca's are undecidable. In contrast to this, the authors give a decision procedure for the equivalence of doca's and show that its time complexity is bounded above by a function exponential in about the square root of the number of states of the tested doca's. They conjecture that the equivalence is decidable for the class of all deterministic pushdown automata.

Valiant published the paper The equivalence problem for deterministic finite-turn pushdown automata in 1974. S A Greibach points out the importance of this paper:-

A pushdown store automaton (pda) is finite-turn if there is a uniform bound on the number of times it can switch from pushing (increasing the length of the pushdown store) to popping (decreasing the pushdown store length) during any computation on any input. The author establishes the decidability of the equivalence problem (do two machines accept the same language?) for deterministic finite-turn pda's. The significance of the result lies in the proof techniques used in establishing it and in the fact that it represents one of the major breakthroughs towards settling the long outstanding conjecture that the equivalence problem for deterministic pda's (dpda's) is decidable (the corresponding problem is known to be undecidable for nondeterministic pda's even in very restricted cases).

After returning from the United States in 1974, Valiant took up a lectureship at Leeds University where he worked for the two years 1974-76. Let us give another example of his early papers, this one again written in collaboration with M S Paterson,. This 1975 paper Deterministic one-counter automata begins with the following authors' introduction:-

We present an analysis of deterministic one-counter automata in order to show that the equivalence problem for them is decidable. All our arguments and results can be translated directly into schema theoretic terms. The corollary that then follows is that equivalence is decidable for Janov schemas even when these are allowed an auxiliary counter.

Valiant moved to Scotland in 1975 to take up a lectureship at the University of Edinburgh. In 1977 he married Gayle Lynne Dyckhoff; they had two sons Gregory John Valiant and Paul A Valiant. In Edinburgh he was promoted to reader in 1981 but went to the United States in 1982 when he was a visiting professor at Harvard. Later that year he was appointed Gordon McKay Professor of Computer Science and Applied Mathematics at Harvard. He remained at Harvard, although he spent the year 1987-88 as a visiting fellow at the University of Oxford in England. In 2001 he was named T Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the Harvard School of Engineering and Applied Sciences.

The contributions that Valiant has made are quite remarkable and he has received the highest honours for his achievements. He was a Guggenheim Fellow in 1985-86 and received the Nevanlinna Prize in 1986. He was elected a fellow of the Royal Society of London in 1991 and, in the following year, a fellow of the American Association for Artificial Intelligence. He was awarded the Knuth Prize from the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory and the Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing in 1997. He was elected to the United States National Academy of Sciences in 2001, received the European Association for Theoretical Computer Science Award, and the Association for Computing Machinery's 2010 A M Turing Award which will be presented to Valiant at the Association's annual awards banquet in San Jose, California on 4 June 2011. The award also includes a cash prize of $250,000.

We have not explained the contributions by Valiant that have led to him receiving the highest possible awards. To do this we quote from the commentary which accompanies the announcement of the Turing Award (the 2011 articles referenced below quote from that commentary). The commentary begins:-

Over the past 30 years, Leslie Valiant has made fundamental contributions to many aspects of theoretical computer science. His work has opened new frontiers, introduced ingenious new concepts, and presented results of great originality, depth, and beauty. Time and again, Valiant's work has literally defined or transformed the computer science research landscape.

It then goes on the give details of several areas to which Valiant has made stunning contributions. We give some short extracts from each of four areas:

1. Computational learning theory. Valiant's greatest single contribution may be his paper 'A theory of the learnable' (1984), which laid the foundations of computational learning theory. ... Valiant's "probably approximately correct" (PAC) model supplied beautiful foundations for the very concept of learning.
2. Complexity of enumeration. In the early 1970's, computational complexity generally dealt with the difficulty of decision problems, such as whether a graph has a perfect matching or whether a traveling salesman can find a route of at most a certain length. ... One of Valiant's most noteworthy discoveries is that counting problems are much more subtle than previous experience suggested. A counting problem asks for the number of some combinatorial objects: for example, how many perfect matchings are there in a graph? We are not just asking the decision problem of whether that number is positive, but also how large it is. If the decision problem is difficult, then the counting problem must be as well, but Valiant's surprising realization was that the converse fails. In his paper "The complexity of computing the permanent" (1979), he showed that although there is an efficient algorithm to tell whether a graph has a perfect matching, there is no efficient algorithm to count perfect matchings (unless P = NP), and in fact counting perfect matchings is as hard as any counting problem. This came as a shock to the computational complexity community, which had grown accustomed to the idea that decision problems would easily capture the key features of a problem.
3. Algebraic computation. Another key contribution to computational complexity was Valiant's theory of algebraic computation, in which he established a framework for understanding which algebraic formulas can be evaluated efficiently. ... In his paper "Completeness classes in algebra" (1979), Valiant characterized the difficulty of algebraic computation in terms of two fundamental and closely related functions from linear algebra, namely the determinant and the permanent.
4. Parallel and distributed computing. In addition to computational learning theory and computational complexity, a third broad area in which Valiant has made important contributions is the theory of parallel and distributed computing. His results here range from simple, but powerful and elegant, insights to reexamining the very foundations. An example of a simple insight is his parallel routing scheme, described in the paper "A scheme for fast parallel communication" (1982).

We end this biography by quoting in full the conclusion of the Turing Award citation:-

Rarely does one see such a striking combination of depth and breadth as in Valiant's work. He is truly a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science.

Articles:

1. J Fishman, 'Probably Approximately Correct' Inventor, From Harvard University, Wins Turing Award, Chronicle of Higher Education (9 March, 2011).
2. C Hennick, Professor gets computing's 'Nobel' : Harvard's Leslie Valiant wins A M Turing Award, Boston Globe (9 March 2011).
3. S Lohr, Another Win for Artificial Intelligence: the Turing Award, New York Times (14 March 2011).
4. A Nozeki, The contributions of Leslie G Valiant (Japanese), Sugaku 39 (1) (1987), 32-39.
5. V Reitano, Harvard's Valiant wins Turing Award, SDTimes (9 March 2011).
6. V Strassen, The work of Leslie G Valiant, Proceedings of the International Congress of Mathematicians, Berkeley, Calif., 1986 Vol 1 (Amer. Math. Soc., Providence, RI, 1987), 16-22.