LOWER BOUNDS FOR MATRIX FACTORIZATION

被引:1
作者
Volk, Ben Lee [1 ]
Kumar, Mrinal [2 ]
机构
[1] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA
[2] Indian Inst Technol, Dept Comp Sci & Engn, Mumbai, Maharashtra, India
关键词
Algebraic complexity; Linear circuits; Matrix factorization; Lower bounds;
D O I
10.1007/s00037-021-00205-2
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of lower bounds for algebraic circuits which compute linear transformations, matrix rigidity and data structure lower bounds. We first show, for every constant d, a deterministic construction in time exp(n(1-Omega(1/d))) of a family {M-n} of n x n matrices which cannot be expressed as a product M-n = A(1) ... A(d) where the total sparsity of A(1) ... A(d) is less than n(1+1/(2d)). In other words, any depth- d linear circuit computing the linear transformation M-n . x has size at least n(1+Omega(1/d)). The prior best lower bounds for this problem were barely super-linear, and were obtained by a long line of research based on the study of super-concentrators. We improve these lower bounds at the cost of a blow up in the time required to construct these matrices. Previously, however, such constructions were not known even in time 2(O(n)) with the aid of an NP oracle. We then outline an approach for proving improved lower bounds through a certain derandomization problem, and use this approach to prove asymptotically optimal quadratic lower bounds for natural special cases, which generalize many of the common matrix decompositions.
引用
收藏
页数:40
相关论文
共 57 条
[1]  
Agrawal M, 2005, LECT NOTES COMPUT SC, V3821, P92, DOI 10.1007/11590156_6
[2]   HITTING-SETS FOR ROABP AND SUM OF SET-MULTILINEAR CIRCUITS [J].
Agrawal, Manindra ;
Gurjar, Rohit ;
Korwar, Arpita ;
Saxena, Nitin .
SIAM JOURNAL ON COMPUTING, 2015, 44 (03) :669-697
[3]   Arithmetic Circuits: A Chasm at Depth Four [J].
Agrawal, Manindra ;
Vinay, V. .
PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, :67-+
[4]   Efficient Construction of Rigid Matrices Using an NP Oracle [J].
Alman, Josh ;
Chen, Lijie .
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, :1034-1055
[5]   Probabilistic Rank and Matrix Rigidity [J].
Alman, Josh ;
Williams, Ryan .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :641-652
[6]   SUPERCONCENTRATORS OF DEPTH-2 AND DEPTH-3 - ODD LEVELS HELP (RARELY) [J].
ALON, N ;
PUDLAK, P .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (01) :194-202
[7]   Descartes' rule of signs revisited [J].
Anderson, B ;
Jackson, J ;
Sitharam, M .
AMERICAN MATHEMATICAL MONTHLY, 1998, 105 (05) :447-451
[8]  
[Anonymous], 1977, Lecture Notes in Computer Science, DOI [10.1007/3-540-08353-7\_135, DOI 10.1007/3-540-08353-7135]
[9]   THE COMPLEXITY OF PARTIAL DERIVATIVES [J].
BAUR, W ;
STRASSEN, V .
THEORETICAL COMPUTER SCIENCE, 1983, 22 (03) :317-330
[10]   An Efficient Reduction from Two-Source to Non-malleable Extractors Achieving Near-Logarithmic Min-entropy [J].
Ben-Aroya, Avraham ;
Doron, Dean ;
Ta-Shma, Amnon .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :1185-1194