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 In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., ...

. 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 higher le ...

. 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 city ...

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 cu ...

, and the

University of Warwick The University of Warwick ( ; abbreviated as ''Warw.'' in post-nominal letters) is a public research university on the outskirts of Coventry between the West Midlands (county), West Midlands and Warwickshire, England. The university was founded i ...

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) model of machine learning that has helped the field of computational learning theory grow, and the concept of

holographic algorithm In computer science, a holographic algorithm is an algorithm that uses a holographic reduction. A holographic reduction is a constant-time reduction that maps solution fragments many-to-many such that the sum of the solution fragments remains un ...

s. In computer systems, he is most well-known for introducing the

bulk synchronous parallel The bulk synchronous parallel (BSP) abstract computer is a bridging model for designing parallel algorithms. It is similar to the parallel random access machine (PRAM) model, but unlike PRAM, BSP does not take communication and synchronization fo ...

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 αὐτόματο� ...

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 (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 u ...

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

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 The Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS) is the engineering school within Harvard University's Faculty of Arts and Sciences, offering degrees in engineering and applied sciences to graduate students admitted ...

. Prior to 1982 he taught at

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 ...

Awards and honors

Valiant received the

Nevanlinna Prize The IMU Abacus Medal, known before 2022 as the Rolf Nevanlinna Prize, is awarded once every four years at the International Congress of Mathematicians, hosted by the International Mathematical Union (IMU), for outstanding contributions in Mathemati ...

in 1986, the

Knuth Prize The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth. History The Knuth Prize has been awarded since 1996 and includes an award of U ...

in 1997, the

EATCS Award The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

in 2008, and the

in 2010. He was elected a Fellow of the Royal Society (FRS) in 1991, a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI) in 1992, and a member of the United States National Academy of Sciences in 2001. Valiant's nomination for the

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, re ...

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.

References

External links

{{DEFAULTSORT:Valiant, Leslie 1949 births Living people Members of the United States National Academy of Sciences Turing Award laureates Nevanlinna Prize laureates Knuth Prize laureates British computer scientists Theoretical computer scientists Alumni of the Department of Computing, Imperial College London Alumni of the University of Warwick Academics of the University of Edinburgh John A. Paulson School of Engineering and Applied Sciences faculty Fellows of the Royal Society Fellows of the Association for the Advancement of Artificial Intelligence Fellows of the American Association for the Advancement of Science People from Belmont, Massachusetts People from Budapest