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

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.

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

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.

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

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.

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.