Leslie Valiant

Imagine wanting to teach a machine something but never knowing whether it truly learned it. That was machine learning before Leslie Valiant: promising, intuitive, but with no mathematical foundation to say when a machine could be considered to "know" something. Valiant, a mathematician and computer scientist born in Budapest in 1949 and educated at Cambridge and Warwick, decided to solve that problem from the ground up.

In 1984 he published "A Theory of the Learnable" in Communications of the ACM, a paper of just a few pages that changed the field forever. There he introduced the PAC model (Probably Approximately Correct), a mathematical framework that precisely defines how many examples an algorithm needs to see, how long it can take, and how reliable its answer must be before we can say it has learned. In other words: he put rules on learning itself. That theory is today the backbone of computational learning theory, the academic field that studies learning from the perspective of efficient algorithms.

Valiant joined Harvard in 1982, where he is the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics, one of the university's most distinguished academic chairs. His contributions go beyond PAC learning: he also created the complexity class #P (which captures counting problems, not just decision problems), proposed the BSP (Bulk Synchronous Parallel) model of parallel computation, and in books like "Circuits of the Mind" (1994) and "Probably Approximately Correct" (2013), explored the connection between computational learning and how the human brain works. In 1986 he received the Nevanlinna Prize at the International Congress of Mathematicians. And in 2010 he won the Turing Award (the "Nobel of computing") for his fundamental contributions to the theory of computational learning and to computer science more broadly.

What I find fascinating about Valiant is that he solved the most important question of all before almost anyone was calling it "machine learning": whether this actually works, and how you can know. Every time an AI model today is trained, evaluates its error, and generalizes to new data, it is following, at some level, the parameters that Valiant formalized more than forty years ago. The next time you use Claude or any AI tool and notice it "understands" what you're asking, there's a little piece of that theory working behind the scenes.