License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.72
URN: urn:nbn:de:0030-drops-156680
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15668/
Go to the corresponding LIPIcs Volume Portal

Frankl, Peter ; Gryaznov, Svyatoslav ; Talebanfard, Navid

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

pdf-format:
LIPIcs-ITCS-2022-72.pdf (0.7 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{frankl_et_al:LIPIcs.ITCS.2022.72,
  author =	{Frankl, Peter and Gryaznov, Svyatoslav and Talebanfard, Navid},
  title =	{{A Variant of the VC-Dimension with Applications to Depth-3 Circuits}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{72:1--72:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15668},
  URN =		{urn:nbn:de:0030-drops-156680},
  doi =		{10.4230/LIPIcs.ITCS.2022.72},
  annote =	{Keywords: VC-dimension, Hypergraph, Clique, Affine Disperser, Circuit}
}

Keywords: VC-dimension, Hypergraph, Clique, Affine Disperser, Circuit
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI