2019/11/26 by Prerona Chatterjee, Chatterjee, Prerona, Mrinal Kumar +5 · 3 citations
Computer Science · #Advanced Data Storage Technologies #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1911.11793
openalex publication_date 2019/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that any Algebraic Branching Program (ABP) computing the polynomial ∑i = 1n xin has at least Ω(n2) vertices. This improves upon the lower bound of Ω(nlog 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 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=1n xin can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑i = 1n xin + ε(x1, …, xn), for a structured "error polynomial" ε(x1, …, xn). To complete the proof, we then observe that the lower bound in [K19] is robust enough and continues to hold for all polynomials ∑i = 1n xin + ε(x1, …, xn), where ε(x1, …, xn) has the appropriate structure. We also use our ideas to show an Ω(n2) 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 Ω(n2/log n) [Nec66, K85, SY10]. Interestingly, this lower bound is asymptotically better than n2/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(n2). Prior to this work, Ben-Or's construction was known to be optimal only for algebraic formulas of depth-3 [SW01].