A Variant of the VC-dimension with Applications to Depth-3 Circuits

Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard

We introduce the following variant of the VC-dimension. Given $S\subseteq \{0,1{\}}^n$ and a positive integer $d$, we define ${\mathbb{U}}_d(S)$ to be the size of the largest subset…