On the VC-dimension of binary codes

DOI10.1137/18M116486XMaRDI QIDQ4583427zbMATH OpenFDO

Authors Sihuang Hu, Nir Weinberger, Ofer Shayevitz

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

Gilbert-Varshamov boundSauer-Shelah lemmaVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Bounds on codes (94B65)

Abstract: We investigate the asymptotic rates of length-$n$ binary codes with VC-dimension at most $dn$ and minimum distance at least $deltan$. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining Sauer-Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert-Varshamov type arguments over constant-weight and Markov-type sets.

Recommendations

• Upper bounds on the cardinality of a binary code with a given minimum distance
• Asymptotic Improvement of the Gilbert–Varshamov Bound on the Size of Binary Codes
• On the complexity of approximating the VC dimension.
• scientific article; zbMATH DE number 774615
• Bounds for Binary Codes With Narrow Distance Distributions

Cites work

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

Cited in

(4)

• Further improvements on asymptotic bounds for codes using distinguished divisors
• Reverse-free codes and permutations
• scientific article; zbMATH DE number 720914 (Why is no real title available?)
• The VC dimension of quadratic residues in finite fields

This page was built for publication: On the VC-dimension of binary codes

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