Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR19-170 | 18th March 2020 18:19

#### A Quadratic Lower Bound for Algebraic Branching Programs and Formulas

Revision #3
Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
Accepted on: 18th March 2020 18:19
Keywords:

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 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.

We also use our ideas to show an $\Omega(n^2)$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree $0.1n$ on $n$ variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $\Omega(n^2/\log n)$ [Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically better than $n^2/\log n$, the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-$3$ formula) of size $O(n^2)$. Prior to this work, Ben-Or's construction was known to be optimal only for algebraic formulas of depth-$3$ [SW01].

Changes to previous version:

Similar proof techniques used to give a quadratic lowerbound on the size of any algebraic formula computing the elementary symmetric polynomial on n variables of degree 01n.

Revision #2 to TR19-170 | 18th March 2020 17:24

#### A Quadratic Lower Bound for Algebraic Branching Programs

Revision #2
Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
Accepted on: 18th March 2020 17:24
Keywords:

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 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.

We also use our ideas to show an $\Omega(n^2)$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree $0.1n$ on $n$ variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $\Omega(n^2/\log n)$ [Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically better than $n^2/\log n$, the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-$3$ formula) of size $O(n^2)$. Prior to this work, Ben-Or's construction was known to be optimal only for algebraic formulas of depth-$3$ [SW01].

Changes to previous version:

Similar proof techniques used to give a quadratic lowerbound on the size of any algebraic formula computing the elementary symmetric polynomial on n variables of degree 01n.

Revision #1 to TR19-170 | 18th March 2020 17:01

#### A Quadratic Lower Bound for Algebraic Branching Programs and Formulas

Revision #1
Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
Accepted on: 18th March 2020 17:01
Keywords:

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 [Kum19], 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 + \varepsilon(\vx)$, for a structured error polynomial'' $\varepsilon(\vx)$. To complete the proof, we then observe that the lower bound in \cite{K19} is robust enough and continues to hold for all polynomials $\sum_{i = 1}^n x_i^n + \varepsilon(\vx)$, where $\varepsilon(\vx)$ has the appropriate structure.

We also use our ideas to show an $\Omega(n^2)$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree $0.1n$ on $n$ variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $\Omega(n^2/\log n)$ [Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically better than $n^2/\log n$, the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-$3$ formula) of size $O(n^2)$. Prior to this work, Ben-Or's construction was known to be optimal only for algebraic formulas of depth-$3$ [SW01].

Changes to previous version:

Similar proof techniques used to give a quadratic lowerbound on the size of any algebraic formula computing the elementary symmetric polynomial on $n$ variables of degree $0.1n$.

### Paper:

TR19-170 | 27th November 2019 07:25

#### A Quadratic Lower Bound for Algebraic Branching Programs

TR19-170
Authors: Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk
Publication: 27th November 2019 12:09
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 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.