Person: Valiant, Leslie Gabriel
Leslie Valiant is a British American computer scientist who has made fundamental contributions to many aspects of theoretical computer science.
Mathematical Profile (Excerpt):
- 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.
- 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.
- 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 Ⓣ(First Symposium of the Society for computer science on automata theory and formal languages) in Bonn in 1973.
- Valiant published the paper The equivalence problem for deterministic finite-turn pushdown automata in 1974.
- 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.
- Valiant moved to Scotland in 1975 to take up a lectureship at the University of Edinburgh.
- The contributions that Valiant has made are quite remarkable and he has received the highest honours for his achievements.
- 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.
- We have not explained the contributions by Valiant that have led to him receiving the highest possible awards.
- 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.
- 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.
- One of Valiant's most noteworthy discoveries is that counting problems are much more subtle than previous experience suggested.
- If the decision problem is difficult, then the counting problem must be as well, but Valiant's surprising realization was that the converse fails.
- 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.
- 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.
- See Valiant's Turing Award Commentary.
Born 28 March 1949, Budapest, Hungary.
View full biography at MacTutor
Tags relevant for this person:
Origin Hungary
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
- non-Github:
- @J-J-O'Connor
- @E-F-Robertson
References
Adapted from other CC BY-SA 4.0 Sources:
- O’Connor, John J; Robertson, Edmund F: MacTutor History of Mathematics Archive
