Leslie Valiant

Hungarian-born British computer scientist at Harvard University since 1982 and the founder of computational learning theory. His paper 'A Theory of the Learnable' (1984) introduced probably approximately correct (PAC) learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right., which defines learning as producing, with high probability and from a feasible number of examples and amount of computation, a hypothesis that is approximately correct on new data drawn from the same distribution; this made learnability a question of computational complexity and, together with VC dimensionVC dimension, n.: A measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably. theory, underpins the analysis of generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers.. He also made foundational contributions to complexity theory, including the class #P and the hardness of computing the permanent (1979), and proposed the bulk synchronous parallel model of computation. His books 'Probably Approximately Correct' (2013) and 'The Importance of Being Educable' (2024) extend the framework to evolution and human cognition. Turing AwardTuring Award, prop. n.: Nicknamed the 'Nobel Prize of computing', the top honor in computer science, awarded each year since 1966 by the Association for Computing Machinery. Several AI pioneers have received it. 2010; Nevanlinna Prize 1986.