The Probably Approximately Correct Learning Model in Computational Learning Theory
Not on the map. Why?
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.
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
10 of 169 references.
References · 10
- 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 103
- 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
- 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
- 2014Complexity theoretic limitations on learning DNF'scited by 21
- 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
- 2022Superpolynomial Lower Bounds for Decision Tree Learning and Testingcited by 9
- 2014Learning circuits with few negationscited by 5
- 2023Properly Learning Decision Trees with Queries Is NP-Hardcited by 5
- 2015How to refute a random CSPcited by 3
- 2023Superpolynomial Lower Bounds for Learning Monotone Classescited by 2
Built on by
Citing papers per year: 2026: 3.
3 papers.