Paper Info
Title
Set-Multilinear and Non-commutative Formula Lower Bounds for Iterated Matrix Multiplication
Abstract
An Algebraic Formula for a polynomialP is an element of F[x(1),...,...,x(N)] is an algebraic expression for P(x(1,)...,...,x(N)) 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 polynomia P(x(1),...,...,x(N)) of degree O( logN/log logN). In the past, many superpolynomial lower bounds were found, but they are of the form Omega(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-Omega,(f((d))) against small-depth set-multilinear formulas (and also for circuits). In this work, we extend this result in two directions. Large-depth set-multilinear formulas. In the setting of general set-multilinear formulas, we prove a lower bound of ( logn) (Omega(logd)) for computing the Iterated Matrix Multiplication polynomial IMMn,d. In particular, this implies the first superpolynomial lower bound against unbounded-depth set-multilinear formulas computing IMMn,n. As a corollary, this resolves the homogeneous version of a question of Nisan (asked in 1991) regarding the relative power of Algebraic formulas and Branching programs in the non-commutative setting. Stronger bounds for homogeneous non-commutative settings. small-depth circuits. In the small-depth homogeneous noncommutative case, we prove a lower bound of n(d1/Delta/2O(Delta)), which yields non-FPT bounds for depths up to o(root logd). In comparison, our previous bound works in the harder commutative set-multilinear setting, but only up to depths o( log logd). Moreover, our lower
Year
DOI
Venue
2022
10.1145/3519935.3520044
PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22)
Keywords
DocType
ISSN
Algebraic complexity, Set-multilinear formulas, Non-commutative formulas, Iterated Matrix Multiplication
Conference
0737-8017
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Sébastien Tavenas100.34
Nutan Limaye213420.59
Srikanth Srinivasan310.71