ECCC-Report TR19-170https://eccc.weizmann.ac.il/report/2019/170Comments and Revisions published for TR19-170en-usWed, 27 Nov 2019 12:09:19 +0200
Paper TR19-170
| A Quadratic Lower Bound for Algebraic Branching Programs |
Prerona Chatterjee,
Mrinal Kumar,
Adrian She,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2019/170We 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 by Kumar [Kum19], which showed a quadratic lower bound for $\text{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 + \varepsilon(\mathbf{x})$, for a structured ``error polynomial'' $\varepsilon(\mathbf{x})$. To complete the proof, we then observe that the lower bound in [Kum19] is robust enough and continues to hold for all polynomials $\sum_{i = 1}^n x_i^n + \varepsilon(\mathbf{x})$, where $\varepsilon(\mathbf{x})$ has the appropriate structure. Wed, 27 Nov 2019 12:09:19 +0200https://eccc.weizmann.ac.il/report/2019/170