# Applications of Littlestone dimension to query learning and to compression

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 12 references that are in the map.
- First posted on arXiv 7 Oct 2023.

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

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)

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

- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)

## Abstract (arXiv)

In this paper we give several applications of Littlestone dimension. The first is to the model of citeangluin2017power, where we extend their results for learning by equivalence queries with random counterexamples. Second, we extend that model to infinite concept classes with an additional source of randomness. Third, we give improved results on the relationship of Littlestone dimension to classes with extended d-compression schemes, proving a strong version of a conjecture of citefloyd1995sample for Littlestone dimension.