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.FSTTCS.2021.14
URN: urn:nbn:de:0030-drops-155251
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15525/
Chillara, Suryajith
Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four
Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to P_d, then C must have size 2^Ω(√dlog{d}).
The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC⁰ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC⁰ can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form - sums of powers of polynomials) of 2^(log^O(1) n) size. Thus they argued that a 2^{ω(polylog n)} "functional" lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the "corresponding Boolean function" of Q against non-uniform ACC⁰. In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits.
In this paper, for large integers n and d such that ω(log²n) ≤ d ≤ n^{0.01}, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O(d/k²) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (∈ VP) over {0,1}^{n²d} must have size n^Ω(k). Since Iterated Matrix Multiplication IMM_{n,d} over {0,1}^{n²d} is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC⁰ from GapL.
For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMM_{n,d} (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMM_{n,d}, for a slightly larger range of individual degree.
BibTeX - Entry
@InProceedings{chillara:LIPIcs.FSTTCS.2021.14,
author = {Chillara, Suryajith},
title = {{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15525},
URN = {urn:nbn:de:0030-drops-155251},
doi = {10.4230/LIPIcs.FSTTCS.2021.14},
annote = {Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication}
}
|
Keywords: |
|
Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication |
|
Collection: |
|
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
29.11.2021 |
