Leslie Valiant
Encyclopedia
Leslie Gabriel Valiant (born 28 March 1949) is a British
computer scientist and computational theorist.
He was educated at King's College, Cambridge
, Imperial College London
, and University of Warwick
where he received his Ph.D.
in computer science in 1974. He started teaching at Harvard University
in 1982 and is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the Harvard School of Engineering and Applied Sciences
. Prior to 1982 he taught at Carnegie Mellon University
, Leeds University, and the University of Edinburgh
.
Valiant is world-renowned for his work in theoretical computer science
. Among his many contributions to complexity theory
, he introduced the notion of #P-completeness to explain why enumeration
and reliability problems are intractable. He also introduced the "probably approximately correct" (PAC
) model of machine learning that has helped the field of computational learning theory grow, and the concept of holographic algorithm
s. His earlier work in automata theory
includes an algorithm for context-free parsing, which is (as of 2010) still the asymptotically fastest known.
He also works in computational neuroscience
focusing on understanding memory and learning.
He received the Nevanlinna Prize
in 1986, the Knuth Prize
in 1997, the EATCS Award in 2008, and the ACM Turing Award in 2010. He is a Fellow of the Royal Society
(London), a Fellow of the American Association for Artificial Intelligence
, and a member of the National Academy of Sciences
(USA).
One of his significant research papers was proving, along with Vijay Vazirani
, UNIQUE-SAT ∈ P
⇒ NP
= RP
(Valiant–Vazirani theorem).
Great Britain
Great Britain or Britain is an island situated to the northwest of Continental Europe. It is the ninth largest island in the world, and the largest European island, as well as the largest of the British Isles...
computer scientist and computational theorist.
He was educated at King's College, Cambridge
King's College, Cambridge
King's College is a constituent college of the University of Cambridge, England. The college's full name is "The King's College of our Lady and Saint Nicholas in Cambridge", but it is usually referred to simply as "King's" within the University....
, Imperial College London
Imperial College London
Imperial College London is a public research university located in London, United Kingdom, specialising in science, engineering, business and medicine...
, and University of Warwick
University of Warwick
The University of Warwick is a public research university located in Coventry, United Kingdom...
where he received his Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
in computer science in 1974. He started teaching at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
in 1982 and is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the Harvard School of Engineering and Applied Sciences
Harvard School of Engineering and Applied Sciences
The Harvard School of Engineering and Applied Science , a school within Harvard University's Faculty of Arts and Sciences , serves as the connector and integrator of Harvard's teaching and research efforts in engineering, applied sciences, and technology.Engineering and applied sciences at Harvard...
. Prior to 1982 he taught at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
, Leeds University, and the University of Edinburgh
University of Edinburgh
The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...
.
Valiant is world-renowned for his work in theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
. Among his many contributions to complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, he introduced the notion of #P-completeness to explain why enumeration
Enumeration
In mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements . The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working...
and reliability problems are intractable. He also introduced the "probably approximately correct" (PAC
Probably approximately correct learning
In computational learning theory, probably approximately correct learning is a framework for mathematical analysis of machine learning. It was proposed in 1984 by Leslie Valiant....
) model of machine learning that has helped the field of computational learning theory grow, and the concept of holographic algorithm
Holographic algorithm
In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a reduction that preserves the number of solutions. These concepts were introduced by Leslie Valiant and are a natural type of reduction for #P problems.Holographic algorithms...
s. His earlier work in automata theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
includes an algorithm for context-free parsing, which is (as of 2010) still the asymptotically fastest known.
He also works in computational neuroscience
Computational neuroscience
Computational neuroscience is the study of brain function in terms of the information processing properties of the structures that make up the nervous system...
focusing on understanding memory and learning.
He received the Nevanlinna Prize
Nevanlinna Prize
The Rolf Nevanlinna Prize is awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences including:...
in 1986, the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
in 1997, the EATCS Award in 2008, and the ACM Turing Award in 2010. He is a Fellow of the Royal Society
Royal Society
The Royal Society of London for Improving Natural Knowledge, known simply as the Royal Society, is a learned society for science, and is possibly the oldest such society in existence. Founded in November 1660, it was granted a Royal Charter by King Charles II as the "Royal Society of London"...
(London), a Fellow of the American Association for Artificial Intelligence
American Association for Artificial Intelligence
The Association for the Advancement of Artificial Intelligence or AAAI is an international, nonprofit, scientific society devoted to advancing the scientific understanding of the mechanisms underlying thought and intelligent behavior and their embodiment in machines...
, and a member of the National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
(USA).
One of his significant research papers was proving, along with Vijay Vazirani
Vijay Vazirani
Vijay Virkumar Vazirani is an Indian American Professor of Computer Science at Georgia Tech.He received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian...
, UNIQUE-SAT ∈ P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
⇒ NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
= RP
RP (complexity)
In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
(Valiant–Vazirani theorem).
External links
- DBLP:Leslie G. Valiant publications in DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...