01 · A life in computing
The person behind the work
Leslie Valiant developed mathematical models for understanding what computers can learn and compute efficiently. His probably approximately correct learning framework made learning from examples a precise subject of complexity theory. He also contributed to counting complexity and parallel computation. At Harvard, his research connected algorithms, artificial intelligence, and models of the brain, asking which capabilities can emerge under realistic limits on time and information.
The contribution, explained
Leslie Valiant developed the probably approximately correct model of learning, alongside major contributions to counting complexity, algebraic computation and parallel computing. PAC learning asks when examples can lead to a hypothesis that is likely to make only a small error on new data from the same distribution.
Why it matters
A mathematical learning model helps separate assumptions about data, sample size and computational efficiency.