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

Abstract

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 $I\subseteq [n]$ such that the projection of $S$ on every subset of $I$ of size $d$ is the $d$-dimensional cube. We show that determining the largest cardinality of a set with a given ${\mathbb{U}}_d$ dimension is equivalent to a Turán-type problem related to the total number of cliques in a $d$-uniform hypergraph. This allows us to beat the Sauer--Shelah lemma for this notion of dimension. We use this to obtain several results on ${\Sigma }_3^k$-circuits, i.e., depth-$3$ circuits with top gate OR and bottom fan-in at most $k$: * Tight relationship between the number of satisfying assignments of a $2$-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. '00). * Improved ${\Sigma }_3^3$-circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement. * We make progress towards settling the ${\Sigma }_3^2$ complexity of the inner product function and all degree-$2$ polynomials over ${\mathbb{F}}_2$ in general. The question of determining the ${\Sigma }_3^3$ complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21).

References in corpus (1)

• Shadows and intersections: stability and new proofs