Leslie Valiant

Leslie Gabriel Valiant ( born March 28, 1949) is a British computer scientist and Turing award winner.

Studies and Research

Valiant studied at the University of Cambridge (King 's College ), at Imperial College London and the University of Warwick, where he worked in computer science at Michael Paterson doctorate (Decision Procedures for Families of Deterministic Pushdown Automata ). 1974 After that, he was at Carnegie Mellon University, the University of Leeds and the University of Edinburgh. From 1982 he taught at Harvard University, where he became professor of computer science and applied mathematics is the time T. Jefferson Coolidge.

Valiant has focused particularly on 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, evolutionary models and artificial intelligence. He originated the concept of holographic algorithms.

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

His PhD is one of Mark Jerrum.

Awards

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

Writings

• Circuits of the at least Oxford University Press, 1994, 2000