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.
Subject groups
- Computer sciences
Computer science (excl engineering aspects)
