Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four
Publisher Information
- Conference: FSTTCS 2021, Pages 14:1-14:15 (LIPIcs, Vol 213)
Abstract
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d^{O(1)}-variate and degree d polynomial P_{d} \in 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^{\Omega(\sqrt{d}\log{d})}.
The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC^0 circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC^0 can also be computed by algebraic \Sigma\mathord{\wedge}\Sigma\Pi 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^{\omega(\log^{O(1)}{n})} functional lower bound for an explicit polynomial Q against \Sigma\mathord{\wedge}\Sigma\Pi circuits would imply a lower bound for the corresponding Boolean function of Q against non-uniform ACC^0. In their work, they ask if their lower bound be extended to \Sigma\mathord{\wedge}\Sigma\Pi circuits.
In this paper, for large integers n and d such that \Omega(\log^2{n})\leq d\leq n^{0.01}, we show that any \Sigma\mathord{\wedge}\Sigma\Pi circuit of bounded individual degree at most O(\frac{d}{k^2}) that functionally computes Iterated Matrix Multiplication polynomial IMM_{n,d} (\in VP) over {\{0,1\}}^{n^2d} must have size n^{\Omega(k)}. Since Iterated Matrix Multiplication IMM_{n,d} over \{0,1\}^{n^2d} 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^0 from GapL.
For the sake of completeness, we also show a syntactic size lower bound against any \Sigma\mathord{\wedge}\Sigma\Pi 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.