Short answers, pulled from the story.
Computational learning theory is a subfield of artificial intelligence devoted to the design and analysis of machine learning algorithms. It studies performance bounds, time complexity, and the feasibility of learning, asking both how accurate an algorithm can be and how long it takes to reach that accuracy.
Leslie Valiant proposed probably approximately correct learning, known as PAC learning. The framework takes a probabilistic approach, asking for a classifier that is correct with high probability on most inputs rather than demanding a perfect answer.
PAC theory inspired boosting, VC theory led to support vector machines, and Bayesian inference led to belief networks. These tools moved directly from theoretical frameworks into widely deployed machine learning applications.
Negative results often rely on two unproven but widely believed assumptions: that P does not equal NP (the P versus NP problem), and that one-way functions exist (a cryptographic assumption). These assumptions link the limits of learning to the broader theory of computational complexity.
VC theory, developed by Vladimir Vapnik and Alexey Chervonenkis, measures how complex a class of functions is by how many data points it can correctly classify in all possible labelings. PAC learning, proposed by Leslie Valiant, focuses on whether an algorithm can find a classifier that is approximately correct with high probability, without requiring it to shatter any particular set of points.
Exact learning is a framework proposed by Dana Angluin in which an algorithm queries an oracle to identify an unknown concept precisely. Unlike PAC learning, it demands a fully correct answer rather than an approximately correct one.