期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit dO(1)-variate and degree d polynomial PdVNP 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 Pd, then C must have size 2(dlogd) . The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC0 circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC0 can also be computed by algebraic circuits (i.e., circuits of the form -- sums of powers of polynomials) of 2logO(1)n size. Thus they argued that a 2(logO(1)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 ACC0. In their work, they ask if their lower bound be extended to circuits. In this paper, for large integers n and d such that (log2n)dn001, we show that any circuit of bounded individual degree at most O(dk2) that functionally computes Iterated Matrix Multiplication polynomial IMMnd (VP) over 01n2d must have size n(k). Since Iterated Matrix Multiplication IMMnd over 01n2d 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 ACC0 from GapL. For the sake of completeness, we also show a syntactic size lower bound against any circuit computing IMMnd (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 IMMnd, for a slightly larger range of individual degree.
