On The Vc-dimension Of Binary Codes | Awesome Learning to Hash Add your paper to Learning2Hash

Awesome Learning to Hash

A Webpage dedicated to the latest research on Hash Function Learning. Maintained by Sean Moran.

Contact Sean Moran about this survey or website. Made with Jekyll and Hyde.

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