# Find a witness or shatter: the landscape of computable PAC learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 11 references that are in the map.
- First posted on arXiv 6 Feb 2023.

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

- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)

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

- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Computable learning of natural hypothesis classes](https://mlsanity.com/paper/2407.16663/) (2024)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [On the Computability of Multiclass PAC Learning](https://mlsanity.com/paper/2502.06089/) (2025)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)
- [Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning](https://mlsanity.com/paper/2511.02644/) (2025)
- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)
- [Uniform Computability of PAC Learning](https://mlsanity.com/paper/2601.18663/) (2026)

## Abstract (arXiv)

This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypothesis which is properly CPAC learnable, but only with uncomputably fast growing sample complexity. This solves a question from Sterkenburg (COLT 2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting.