Name
Abstract | ||
|---|---|---|
We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results in [K19], which showed a quadratic lower bound for \emph{homogeneous} ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial $\sum_{i=1}^n x_i^n$ can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial $\sum_{i = 1}^n x_i^n + \epsilon(x_1, \ldots, x_n)$, for a structured "error polynomial" $\epsilon(x_1, \ldots, x_n)$. To complete the proof, we then observe that the lower bound in [K19] is robust enough and continues to hold for all polynomials $\sum_{i = 1}^n x_i^n + \epsilon(x_1, \ldots, x_n)$, where $\epsilon(x_1, \ldots, x_n)$ has the appropriate structure. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.CCC.2020.2 | Electronic Colloquium on Computational Complexity (ECCC) |
DocType | Volume | Citations |
Journal | 26 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prerona Chatterjee | 1 | 0 | 1.35 |
| Mrinal Kumar 0001 | 2 | 64 | 9.94 |
| Adrian She | 3 | 0 | 0.68 |
| Ben Lee Volk | 4 | 12 | 5.62 |