A variant of the VC-dimension with applications to depth-3 circuits

0553336 - MÚ 2023 RIV DE eng C - Conference Paper (international conference)
Frankl, P. - Gryaznov, Svyatoslav - Talebanfard, Navid
A variant of the VC-dimension with applications to depth-3 circuits.
13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2022 - (Braverman, M.), č. článku 72. Leibniz International Proceedings in Informatics, 215. ISBN 978-3-95977-217-4. ISSN 1868-8969.
[13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Berkeley (US), 31.01.2022-03.02.2022]
R&D Projects: GA ČR(CZ) GX19-27871X; GA ČR(CZ) GA19-05497S
Institutional support: RVO:67985840
Keywords : VC-dimension * hypergraph * clique
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.4230/LIPIcs.ITCS.2022.72

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).
Permanent Link: http://hdl.handle.net/11104/0328294