The Probably Approximately Correct Learning Model in Computational Learning Theory
Rocco A. Servedio · 2025
Read The Probably Approximately Correct Learning Model in Computational Learning Theory by Rocco A. Servedio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08791.txt.
Introduction
Rocco Servedio surveys what is known about learning Boolean functions in the Probably Approximately Correct model. Leslie Valiant introduced that framework to define what it means for a machine to learn from examples with high confidence and low error. The survey covers the model itself and its commonly studied variants.
Boolean function classes are the classic testbeds for learning theory. They range from simple conjunctions to rich circuit families. Decades of work have mapped which of them can be learned efficiently and which resist every known algorithm. A survey like this organizes those results, the techniques behind them, and the gaps that remain. It serves researchers and graduate students who need the lay of the land in computational learning theory before pushing on open problems.
Catalog record
| CREATOR | Rocco A. Servedio |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-08791