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