Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

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 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 $$\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 ({\bf x})$$ , for a structured “error polynomial” $$\varepsilon ({\bf 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 $$\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})$$ , where $$\varepsilon ({\bf 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)$$ 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).