期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：An Algebraic Formula for a polynomial PF[x1xN] is an algebraic expression for P(x1xN) using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class NC1 Proving lower bounds against this model is thus an important problem. It is known that, to prove superpolynomial lower bounds against algebraic formulas, it suffices to prove good enough lower bounds against restricted kinds of formulas known as Set-Multilinear formulas, for computing a polynomial P(x1xN) of degree O(logNloglogN) . In the past, many superpolynomial lower bounds were found, but they are of the form (f(d)poly(N)) (where f is typically a subexponential function) which is insufficient to get lower bounds for general formulas. Recently, the authors proved the first non-FPT lower bounds, i.e., a lower bound of the form N(f(d)), against small-depth set-multilinear formulas (and also for circuits). In this work, we extend this result in two directions. 1) Large-depth set-multilinear formulas. In the setting of general set-multilinear formulas, we prove a lower bound of (logn)(logd) for computing the Iterated Matrix Multiplication polynomial IMMnd In particular, this implies the first superpolynomial lower bound against unbounded-depth set-multilinear formulas computing IMMnn As a corollary, this also resolves the homogeneous version of a question of Nisan (STOC 1991) regarding the relative power of Algebraic formulas and Branching programs in the non-commutative setting. 2) Stronger bounds for homogeneous non-commutative small-depth circuits. In the small-depth homogeneous non-commutative case, we prove a lower bound of nd12O() , which yields non-FPT bounds for depths up to o(logd) In comparison, the previous bound works in the harder commutative set-multilinear setting, but only up to depths o(loglogd). Moreover, our lower bound holds for all values of d, as opposed to the previous set-multilinear lower bound, which holds as long as d is small, i.e., d=O(logn).
关键词：Arithmetic Circuit Complexity;Iterated Matrix Multiplication;non-commutative formulas;set-multilinear formula
