# The Probably Approximately Correct Learning Model in Computational Learning Theory

arXiv: https://arxiv.org/abs/2511.08791 · HTML: https://mlsanity.com/paper/2511.08791/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 169 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 10 of 10)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Learning circuits with few negations](https://mlsanity.com/paper/1410.8420/) (2014)
- [Properly Learning Decision Trees with Queries Is NP-Hard](https://mlsanity.com/paper/2307.04093/) (2023)
- [How to refute a random CSP](https://mlsanity.com/paper/1505.04383/) (2015)
- [Superpolynomial Lower Bounds for Learning Monotone Classes](https://mlsanity.com/paper/2301.08486/) (2023)

## Built on by (most cited first, 3 of 3)

- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)
- [A Quantum/Classical Example Oracle Separation for Making Things Up](https://mlsanity.com/paper/2608.11648/) (2026)

## Abstract (arXiv)

This survey paper gives an overview of various known results on learning classes of Boolean functions in Valiant's Probably Approximately Correct (PAC) learning model and its commonly studied variants.