Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.

We show that any Algebraic Branching Program (ABP) computing the polynomial ∑ i = 1 n x i n has at least Ω (n 2) vertices. This improves upon the lower bound of Ω (n log n) , which follows from the classical result of Strassen (1973a) and Baur & Strassen (1983), and extends the results in Kumar (2019), which showed a quadratic lower bound for 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 ∑ i = 1 n x i n can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑ i = 1 n x i n + ε (x) , for a structured “error polynomial” ε (x) . To complete the proof, we then observe that the lower bound in Kumar (2019) is robust enough and continues to hold for all polynomials ∑ i = 1 n x i n + ε (x) , where ε (x) has the appropriate structure. We also use our ideas to show an Ω (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 Ω (n 2 / log n) Kalorkoti (1985); Nechiporuk (1966); Shpilka & Yehudayoff (2010). 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 (Shpilka & Wigderson 2001). [ABSTRACT FROM AUTHOR]