2026-07-23T19:07:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15668 2024-03-06T10:55:54Z ddc:004 open_access

A Variant of the VC-Dimension with Applications to Depth-3 Circuits Frankl, Peter Gryaznov, Svyatoslav Talebanfard, Navid VC-dimension Hypergraph Clique Affine Disperser Circuit We introduce the following variant of the VC-dimension. Given S ⊆ {0,1}ⁿ 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 Σ₃^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 Σ₃³-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 Σ₃² complexity of the inner product function and all degree-2 polynomials over 𝔽₂ in general. The question of determining the Σ₃³ complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Frankl and Svyatoslav Gryaznov and Navid Talebanfard 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.72 urn:nbn:de:0030-drops-156680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.72 eng https://creativecommons.org/licenses/by/4.0/legalcode