Applications of littlestone dimension to query learning and to compression

DOI10.1016/J.IC.2026.105424MaRDI QIDQ6841896zbMATH OpenFDO

Authors Hunter Chase, James Freitag, Lev Reyzin

Publication date 20 March 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105424

zbMATH Keywords

compression schemeLittlestone dimensionquery learningrandom queries

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
• Compression schemes, stable definable families, and o-minimal structures
• Density of compressible types and some consequences
• Externally definable sets and dependent pairs. II
• MODEL THEORY AND MACHINE LEARNING
• On uniform definability of types over finite sets for NIP formulas
• Sample Compression Schemes for VC Classes
• The power of random counterexamples
• Unlabeled compression schemes for maximum classes

This page was built for publication: Applications of littlestone dimension to query learning and to compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6841896)