Leslie Gabriel Valiant %27EC%2F1991%2F35%27)" target="_blank" class="mw-redirect" title="DServe Archive Catalog Show">DServe Archive Catalog Show /ref> (born 28 March 1949) is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at
Harvard University
Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...
. Valiant was awarded the
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
in 2010, having been described by the A.C.M. as 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; in particular for his "striking combination of depth and breadth".
Education
Valiant was educated at
King's College, Cambridge
King's College is a constituent college of the University of Cambridge. Formally The King's College of Our Lady and Saint Nicholas in Cambridge, the college lies beside the River Cam and faces out onto King's Parade in the centre of the cit ...
,
Imperial College London
Imperial College London (legally Imperial College of Science, Technology and Medicine) is a public research university in London, United Kingdom. Its history began with Prince Albert, consort of Queen Victoria, who developed his vision for a ...
, and the
University of Warwick
, mottoeng = Mind moves matter
, established =
, type = Public research university
, endowment = £7.0 million (2021)
, budget = £698.2 million (202 ...
where he received a PhD in computer science in 1974.
Research and career
Valiant is world-renowned for his work in
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
. Among his many contributions to complexity theory, he introduced the notion of #P-completeness ("sharp-P completeness") to explain why enumeration and reliability problems are intractable. He also introduced the "probably approximately correct" (
PAC Pac or PAC may refer to:
Military
* Rapid Deployment Force (Malaysia), an armed forces unit
* Patriot Advanced Capability, of the MIM-104 Patriot missile
* Civil Defense Patrols (''Patrullas de Autodefensa Civil''), Guatemalan militia and paramili ...
) model of machine learning that has helped the field of computational learning theory grow, and the concept of holographic algorithms. In computer systems, he is most well-known for introducing the bulk synchronous parallel processing model. His earlier work in
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
computational neuroscience
Computational neuroscience (also known as theoretical neuroscience or mathematical neuroscience) is a branch of neuroscience which employs mathematical models, computer simulations, theoretical analysis and abstractions of the brain to ...
focusing on understanding memory and learning.
Valiant's 2013 book is '' Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World''. In it he argues, among other things, that evolutionary biology does not explain the rate at which evolution occurs, writing, for example, "The evidence for Darwin's general schema for evolution being essentially correct is convincing to the great majority of biologists. This author has been to enough natural history museums to be convinced himself. All this, however, does not mean the current theory of evolution is adequately explanatory. At present the theory of evolution can offer no account of the rate at which evolution progresses to develop complex mechanisms or to maintain them in changing environments."
Valiant started teaching at
Harvard University
Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
, the
University of Leeds
, mottoeng = And knowledge will be increased
, established = 1831 – Leeds School of Medicine1874 – Yorkshire College of Science1884 - Yorkshire College1887 – affiliated to the federal Victoria University1904 – University of Leeds
, ...
, and the
University of Edinburgh
The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
Association for the Advancement of Artificial Intelligence (AAAI) in 1992
The Association for the Advancement of Artificial Intelligence (AAAI) is an international scientific society devoted to promote research in, and responsible use of, artificial intelligence. AAAI also aims to increase public understanding of artif ...
Royal Society
The Royal Society, formally The Royal Society of London for Improving Natural Knowledge, is a learned society and the United Kingdom's national academy of sciences. The society fulfils a number of roles: promoting science and its benefits, r ...
reads:
The citation for his A.M. Turing Award reads:
Personal life
His two sons Gregory Valiant and Paul ValiantPaul Valiant's homepage /ref> are both also theoretical computer scientists.