Click the picture above
to see five larger pictures
Show birthplace location
|Previous||(Alphabetically)||Next||Biographies index |
|Version for printing|
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:
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.
Although we have quoted at some length from the Commentary for the Turing Award, the reader may still wish to read the full commentary. See Valiant's Turing Award Commentary.
Article by: J J O'Connor and E F Robertson
List of References (6 books/articles)|
|Mathematicians born in the same country|
Additional Material in MacTutor
Other Web sites
|Previous||(Alphabetically)||Next||Biographies index |
|History Topics || Societies, honours, etc.||Famous curves |
|Time lines||Birthplace maps||Chronology||Search Form |
|Glossary index||Quotations index||Poster index |
|Mathematicians of the day||Anniversaries for the year|
JOC/EFR © March 2011 |
School of Mathematics and Statistics|
University of St Andrews, Scotland
The URL of this page is:|