# Leslie Valiant

> 1949– · Computer Scientist
>
> **Recorded contribution:** PAC learning theory; #P-completeness; holographic algorithms; Valiant model

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

Leslie Valiant (born 1949) developed several new lenses on computational difficulty and learning. He defined #P to classify counting versions of NP problems and proved the permanent #P-complete; introduced probably approximately correct learning, where an algorithm must, with high probability, find a hypothesis whose future error is small using feasible samples and computation; and advanced holographic algorithms and parallel computation. PAC learning does not say a model is probably correct in an absolute sense—it quantifies error and confidence relative to a distribution, concept class, and assumptions. Valiant's central contribution is turning informal feasibility questions into explicit resource-and-guarantee contracts.

## 2. The problem inherited

Learning theory lacked a general operational definition of efficient learnability, and complexity theory needed to distinguish finding one witness from counting all witnesses.

## 3. The central contribution

Valiant formalized distributional learning guarantees and counting complexity, creating durable frameworks for comparing algorithms rather than individual techniques.

## 4. Reconstruct the mechanism

1. Assume examples are drawn from a distribution and labeled by a target concept in a specified class.
2. Choose accuracy epsilon and failure probability delta as explicit learner requirements.
3. Use a sample and polynomial resources to produce a hypothesis whose true error is at most epsilon.
4. Require that guarantee to hold with probability at least one minus delta over the sampled training set and learner randomness.

## 5. What changed downstream

- PAC learning became a foundation of computational learning theory and sample-complexity analysis.
- #P-completeness exposed counting as potentially harder than deciding existence.
- Valiant's models influenced boosting, generalization theory, parallel algorithms, and complexity.

## 6. Attribution, limits, and uncertainty

- PAC conclusions depend on distribution, noise, representation, hypothesis class, and computational assumptions.
- Small average error can hide subgroup harms, rare catastrophic cases, calibration failure, or distribution shift.
- #P-hardness is a worst-case classification and does not preclude useful approximation or structured instances.

## 7. Reconstruction lab

For a finite hypothesis class, derive a union-bound sample size for chosen epsilon and delta, train on synthetic examples, and measure violations across repeated samples. Shift the test distribution and document which PAC assumption broke.

## 8. Evidence trail

- [A Theory of the Learnable](https://doi.org/10.1145/1968.1972) — Communications of the ACM
- [Leslie Valiant](https://people.seas.harvard.edu/~valiant/) — Harvard University

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*