דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Coding Theory: On the VC-Dimension of Binary Error-Correcting Codes
event speaker icon
שוהאנג הו (אונ' תל-אביב)
event date icon
יום ראשון, 23.4.2017, 14:30
event location icon
טאוב 601
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.
[בחזרה לאינדקס האירועים]