arbiter
JournalsAccount

Applications of littlestone dimension to query learning and to compression

Hunter Chase et al.

Information and Computation2026https://doi.org/10.1016/j.ic.2026.105424article
ABDC B
Weight
0.50

Abstract

In this paper we give several applications of Littlestone dimension. The first is to the model of Angluin and Dohrn [1], 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 the analog of a conjecture of Floyd and Warmuth [2] for Littlestone dimension.

Open via your library →

Cite this paper

https://doi.org/https://doi.org/10.1016/j.ic.2026.105424

Or copy a formatted citation

@article{hunter2026,
  title        = {{Applications of littlestone dimension to query learning and to compression}},
  author       = {Hunter Chase et al.},
  journal      = {Information and Computation},
  year         = {2026},
  doi          = {https://doi.org/https://doi.org/10.1016/j.ic.2026.105424},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

Applications of littlestone dimension to query learning and to compression

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.