On the VC-Dimension of Binary Codes

DOI10.1137/18M116486XzbMath1436.94123arXiv1703.01586MaRDI QIDQ4583427

Ofer Shayevitz, Nir Weinberger, Sihuang Hu

Publication date: 30 August 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.01586

zbMATH Keywords

Vapnik-Chervonenkis dimensionGilbert-Varshamov boundSauer-Shelah lemma

Mathematics Subject Classification ID

Bounds on codes (94B65)

Cites Work

• Unnamed Item
• Entropy at a weight-per-symbol and embeddings of Markov chains
• \(\epsilon\)-nets and simplex range queries
• Central limit theorems for empirical measures
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Maxentropic Markov chains (Corresp.)
• Generating functions and lower bounds on rates for limited error-correcting codes
• Learnability and the Vapnik-Chervonenkis dimension
• Large deviations, hypotheses testing, and source coding for finite Markov chains
• Conditional limit theorems under Markov conditioning
• The error exponent for the noiseless encoding of finite ergodic Markov sources
• Improved Gilbert-Varshamov bound for constrained systems
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• The method of types [information theory]
• Asymptotically Optimal Tests for Finite Markov Chains
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: On the VC-Dimension of Binary Codes