A Variant of the VC-dimension with Applications to Depth-3 Circuits
share
We introduce the following variant of the VC-dimension. Given S โ{0, 1}^n and a positive integer d, we define ๐_d(S) to be the size of the largest subset I โ [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 ๐_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 ฮฃ_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 ฮฃ_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 ฮฃ_3^2 complexity of the inner product function and all degree-2 polynomials over ๐ฝ_2 in general. The question of determining the ฮฃ_3^3 complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21).
READ FULL TEXT
