Lower Bounds for the Sum of Small-Size Algebraic Branching Programs

We observe that proving strong enough lower bounds for the sum of set-multilinear Algebraic Branching Programs (smABPs) in the low-degree regime implies Valiant’s conjecture (i.e. it implies general ABP lower bounds). Using this connection, we obtain lower bounds for the sum of small-sized general ABPs. In particular, we show that the sum of \({{\,\textrm{poly}\,}}(n)\) ABPs, each of size ( \({:}{=}\) number of vertices) \((nd)^{o(1)}\) , cannot compute the family of Iterated Matrix Multiplication polynomials \(\textrm{IMM}_{n,d}\) for any arbitrary function \(d=d(n)\) . We also give a dual version of our result for the sum of low-variate ROABPs (read-once oblivious ABPs) and read-k oblivious ABPs. Both smABP and ROABP are very well-studied ‘simple’ models; our work puts them at the forefront of understanding Valiant’s conjecture.