| Identifikační kód |
RIV/67985840:_____/22:00553336 |
| Název v anglickém jazyce |
A variant of the VC-dimension with applications to depth-3 circuits |
| Druh |
D - Stať ve sborníku |
| Jazyk |
eng - angličtina |
| Vědní obor |
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) |
| Rok uplatnění |
2022 |
| Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku |
2 |
| Počet tvůrců celkem |
3 |
| Počet domácích tvůrců |
2 |
| Výčet všech uvedených jednotlivých tvůrců |
Svyatoslav Gryaznov (státní příslušnost: RU - Ruská federace, domácí tvůrce: A, orcid: 0000-0002-5648-8194, scopusid: 57190048055, researcherid: T-6117-2019)
Navid Talebanfard (státní příslušnost: IR - Íránská islámská republika, domácí tvůrce: A, orcid: 0000-0001-5763-1397, scopusid: 23391047300, researcherid: P-4305-2017)
P. Frankl (státní příslušnost: HU - Maďarsko) |
| Popis výsledku v anglickém jazyce |
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:n- 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).n- Improved Σ₃³-circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement.n- 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). |
| Klíčová slova oddělená středníkem |
VC-dimension;hypergraph;clique |
| Stránka www, na které se nachází výsledek |
- |
| DOI výsledku |
10.4230/LIPIcs.ITCS.2022.72 |
| Odkaz na údaje z výzkumu |
- |