Leslie Valiant

Life and career

Leslie Gabriel Valiant was born in Budapest in 1949 and raised in Britain. He read mathematics at King's College, Cambridge, took a diploma in computer science at Imperial College London, and completed his PhD at the University of Edinburgh in 1974, working on formal language theory — his thesis concerned the decidability of equivalence for deterministic finite-turn pushdown automata. That early work already showed the trait that runs through his whole career: a willingness to take a question that sounds informal or philosophical and force it into a form where a theorem can be proved about it.

He held positions at Leeds and Edinburgh before moving to Harvard in 1982, where he became the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics and has remained since. Colleagues describe him as reserved, deliberate, and unusually indifferent to fashion. He has repeatedly worked on problems that the field was not yet interested in, and has been vindicated on a timescale of decades rather than years.

Valiant's 1984 paper "A Theory of the Learnable," published in *Communications of the ACM*, is the founding document of computational learning theory. Its reception is instructive. At the time, machine learning in the AI community was largely a matter of heuristics and demonstrations; there was no accepted way to say whether a learning algorithm was good. Valiant supplied one, and in doing so imported the entire apparatus of complexity theory — resource bounds, worst-case guarantees, hardness results — into a field that had none. The COLT conference series grew out of the research program the paper started.

He received the ACM Turing Award in 2010, cited for transformative contributions to the theory of computation, including PAC learning, the complexity of enumeration and algebraic computation, and the theory of parallel and distributed computing. He has also received the Nevanlinna Prize, the Knuth Prize, and the EATCS Award, and is a Fellow of the Royal Society and a member of the National Academy of Sciences. In later years he has written for a general audience — *Circuits of the Mind* on neural computation, and *Probably Approximately Correct*, which extends his learning framework into an argument about biological evolution as a form of bounded learning. He has proposed "ecorithms" as a term for algorithms that learn from an environment they do not control, and has advanced a computational account of evolvability as a restricted case of learnability. His son Gregory Valiant is himself a well-known theorist working on learning and statistics at Stanford.

Key contributions

**PAC learning.** The 1984 definition is deceptively simple and enormously consequential. Fix a class $C$ of possible target concepts. An unknown target $c \in C$ and an unknown distribution $D$ over the input space are both adversarially chosen. The learner draws labeled examples i.i.d. from $D$ and must, with probability at least $1-\delta$, output a hypothesis whose error under $D$ is at most $\epsilon$ — using a number of samples and an amount of computation polynomial in $1/\epsilon$, $1/\delta$, and the problem size. Hence *probably* (the $\delta$) *approximately* (the $\epsilon$) *correct*.

Every design choice here earns its keep. Requiring the guarantee to hold for all distributions $D$ makes the result assumption-free about the data. Measuring error under the *same* distribution the samples came from is what makes generalization possible at all — you are not asked to extrapolate, only to interpolate correctly. And insisting on polynomial *computation*, not just polynomial samples, is the move that makes this a theory of computer science rather than of statistics; it lets one prove that some concept classes are information-theoretically learnable but computationally intractable to learn, a distinction with no analogue in classical statistical theory. Valiant supplied the hardness half of the story as well, arguing that natural classes such as general Boolean formulae resist efficient learning under standard complexity assumptions — a line later sharpened by Kearns, Pitt, and others into representation-dependent NP-hardness results and cryptographic hardness-of-learning results.

The tight characterization of sample complexity in terms of VC dimension — the result that a class is PAC-learnable if and only if its VC dimension is finite, with sample bounds scaling accordingly — came in 1989 from Blumer, Ehrenfeucht, Haussler, and Warmuth, building on Vapnik and Chervonenkis's earlier statistical work. Valiant provided the framework in which that result is the answer to a well-posed question.

**Weak learning and boosting.** Valiant, with Michael Kearns, posed the *hypothesis boosting question*: if you have a learner that does only slightly better than random guessing, can you always amplify it into one that is arbitrarily accurate? Schapire answered yes in 1990, Freund improved it, and the Freund–Schapire AdaBoost algorithm that followed became one of the most practically important algorithms in machine learning. The entire boosting literature — and by extension gradient boosting, XGBoost, and the tree-ensemble methods that still dominate tabular prediction — traces back to a question posed inside Valiant's framework.

**#P and the permanent.** In 1979 Valiant introduced the complexity class **#P**, which counts the number of accepting computations of a nondeterministic polynomial-time machine — a *counting* class rather than a decision class. He then proved that computing the **permanent** of a 0/1 matrix is #P-complete. This result is startling because the permanent's formula is nearly identical to the determinant's, differing only in the absence of alternating signs, yet the determinant is computable in polynomial time by Gaussian elimination while the permanent is as hard as counting anything in NP. The result is the reason counting and approximate counting became a field, and it underwrites hardness results in statistical physics (partition functions), Bayesian inference (computing normalizing constants), and quantum computing (boson sampling hardness rests directly on permanent hardness).

**Holographic algorithms and the BSP model.** Valiant later introduced holographic algorithms, which solve certain counting problems in polynomial time by an interference-like cancellation of computational paths, mapping problems into matchgate computations. Separately, his Bulk Synchronous Parallel model gave parallel computing a bridging abstraction — alternating local computation, communication, and barrier synchronization — that influenced later large-scale systems including graph-processing frameworks.

In battle

Valiant's computed profile is the most category-lopsided on this roster. He carries 100 problems at a mean of 37.3, with just three dominant problems but a very high ceiling. His top category is **classification** at 83.5 — the single highest category average among the theorists here — followed by **nlp** (66.0), **computability** (54.9 across sixteen problems), and **high-dim** (53.5). That classification number is what separates him from Cook, Blum, and Yao: he is the theorist who actually built a bridge into machine learning, and the matrix knows it.

He dominates **P032, "What can be learned at all?"** (97), which is his 1984 paper restated as a scenario — how much data, how much computation, what guarantee. He takes **P028, "Which examples deserve labels?"** (92), the active-learning and label-efficiency question, because sample complexity is the currency of his framework. **P261, "A million parsed sentences"** (80) draws on his early formal-language work and on learnability of structured grammars. He is strong on **P031, "Is there a fast route through every city?"** (78) and **P162, "More time, strictly more power"** (76) from the complexity side, on **P150, "Learn from the stream, one at a time"** (75) where online learning shares his mistake-bound and amplification instincts, and on **P030, "Will it ever halt?"** (70) and **P164, "Trust without recomputing"** (66).

His weaknesses are the flip side of his abstraction. **P211, "Roll the dice at Los Alamos"** (7) is his floor — Monte Carlo simulation for physical processes, involving variance reduction and pseudorandom sampling in a domain with no concept class and no generalization bound. **P210, "Find the lost submarine"** (13) is Bayesian search theory; **P119, "Roll it out in waves"** (12) is stepped-wedge trial design; **P200, "Beat the world champion"** (12) and **P196, "Best answer before the buzzer"** (15) are game-playing and anytime-search problems that reward engineering under real time constraints rather than asymptotic guarantees. **P201, "The dice make it learnable"** (15) is a notable and instructive loss — it sounds like PAC territory but turns on a different probabilistic mechanism than the one his framework formalizes.

The pattern is this: Valiant is superb wherever the question is *what is provably learnable and at what cost*, and weak wherever the answer depends on simulation, real-time engineering, or classical statistical estimation. His `causality` (10.0), `experimental-design` (17.0), and `testing` (17.5) averages are all in the basement. His stated battle identity captures the deepest tension honestly: PAC bounds are worst-case over all distributions, and modern deep networks generalize far better than those bounds permit, which is exactly why they succeed in domains where his theory predicts failure. Fielding Valiant is a bet that the round is about the *theory* of learning rather than the *practice* of it.