We show that any Algebraic Branching Program (ABP) computing the polynomial n i =1 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 Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], 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 n i =1 x i n can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial n i =1 x i n + ( x ) , for a structured ``error polynomial'' ( x ) . To complete the proof, we then observe that the lower bound in [Kum19] is robust enough and continues to hold for all polynomials n i =1 x i n + ( x ) , where ( x ) has the appropriate structure.