On The Vc-dimension Of Binary Codes

Hu Sihuang, Weinberger Nir, Shayevitz Ofer. SIAM J. Discrete Math. 2017

[Paper]    

We investigate the asymptotic rates of length-$n$ binary codes with VC-dimension at most $dn$ and minimum distance at least $\delta n$. 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.

Similar Work

• Lower Bounds On The Minimum Average Distance Of Binary Codes
• New Upper Bounds On A(nd)
• An Elementary Proof Of The First LP Bound On The Rate Of Binary Codes
• Error Correction Maximization For Deep Image Hashing