Sihuang Hu – On the VC-Dimension of Binary Error-Correcting Codes.

Event Details

  • Date:

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.