Leslie Valiant

from Wikipedia, the free encyclopedia
Leslie Valiant 2005 in Oberwolfach

Leslie Gabriel Valiant (born March 28, 1949 in Budapest , Hungary ) is a British computer scientist and Turing Prize winner .

Study and Research

Valiant studied at the University of Cambridge ( King's College ), Imperial College London and the University of Warwick , where he received his PhD in computer science under Michael Paterson in 1974 ( Decision Procedures for Families of Deterministic Pushdown Automata ). He then went to Carnegie Mellon University , the University of Leeds and the University of Edinburgh . From 1982 he taught at Harvard University , where he is currently T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics.

Valiant dealt in particular with complexity theory (introduction of Sharp-P 1979), computational learning theory (introduction of the PAC model of machine learning: Probably Approximately Correct Learning ), parallel computing, neural computing, evolution models and artificial intelligence . He came up with the concept of holographic algorithms.

In 1985 he and Vijay Vazirani proved an important result of the complexity theory (Valiant-Vazirani theorem) that if UNIQUE- SAT is in P , the complexity classes NP and RP (random polynomial) are identical.

Mark Jerrum is one of his PhD students .

Awards

In 1986 he received the Nevanlinna Prize , the Knuth Prize for Computer Science in 1997 , the EATCS Award in 2008 and the Turing Award in 2010 . He is a Fellow of the Royal Society , a member of the National Academy of Sciences and a member of the Academia Europaea since 2019 . In 1983 he was invited speaker at the International Congress of Mathematicians in Warsaw ( An algebraic approach to computational complexity ).

Fonts

  • Circuits of the mind . Oxford University Press, 1994, 2000

Individual evidence

  1. ^ Valiant: The Complexity of Computing the Permanent, Theoretical Computer Science, Volume 8, 1979, pp. 189-201
  2. ^ Valiant, Vazirani NP is as easy as detecting unique solutions , Proceedings of the seventeenth annual ACM symposium on Theory of Computing, 1985, pp. 458-463.

Web links

personal data
SURNAME Valiant, Leslie
ALTERNATIVE NAMES Valiant, Leslie G .; Valiant, Leslie Gabriel (full name)
BRIEF DESCRIPTION British computer scientist
DATE OF BIRTH March 28, 1949
PLACE OF BIRTH Budapest , Hungary