Name
Abstract | ||
|---|---|---|
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 subexponential time of a family ${M_n}$ of $n times n$ matrices which cannot be expressed as a product $M_n = A_1 cdots A_d$ where the total sparsity of $A_1,ldots,A_d$ is less than $n^{1+1/(2d)}$. In other words, any depth-$d$ linear circuit computing the linear transformation $M_ncdot x$ has size at least $n^{1+Omega(1/d)}$. This improves upon the prior best lower bounds for this problem, which are barely super-linear, and were obtained by a long line of research based on the study of super-concentrators (albeit at the cost of a blow up in the time required to construct these matrices). 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.CCC.2020.5 | Electronic Colloquium on Computational Complexity (ECCC) |
Field | DocType | Volume |
Data structure,Discrete mathematics,Combinatorics,Algebraic number,Matrix (mathematics),Matrix decomposition,Quadratic equation,Linear map,Asymptotically optimal algorithm,Mathematics,Sparse matrix | Journal | abs/1904.01182 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Ben Lee Volk | 2 | 12 | 5.62 |