Skip to content
Fellows Directory

Leslie Valiant

Leslie Valiant

Credit: Larry Bercow

Professor Leslie Valiant FRS

Fellow


Elected: 1991

Biography

Leslie Valiant has contributed in a decisive way to the growth of theoretical computer science. His work is concerned mainly with quantifying mathematically the resource costs of solving problems on a computer. In early work (1975), he found the asymptotically fastest algorithm known for recognising context-free languages. At the same time, he pioneered the use of communication properties of graphs for analysing computations.

In 1977, he defined the notion of ‘sharp-P’ (#P)-completeness and established its utility in classifying counting or enumeration problems according to computational tractability. The first application was to counting matchings (the matrix permanent function). In 1984, Leslie introduced a definition of inductive learning that, for the first time, reconciles computational feasibility with the applicability to nontrivial classes of logical rules to be learned.

This notion, later called ‘probably approximately correct learning’, became a theoretical basis for the development of machine learning. In 1989, he formulated the concept of bulk synchronous computation as a unifying principle for parallel computation. Leslie received the Nevanlinna Prize in 1986, and the Turing Award in 2010.

Interest and expertise

Subject groups

  • Mathematics
    • Computer science (excl engineering aspects)

Keywords

Computational complexity , Machine learning, Parallel computation, Computational neuroscience

Was this page useful?
Thank you for your feedback
Thank you for your feedback. Please help us improve this page by taking our short survey.