- with Prateek Dwivedi and Nitin Saxena
- Theoret. Comput. Sci., TCS 2025 (invited special issue of TAMC 2024)
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 ABPs, each of size ( number of vertices) , cannot compute the family of Iterated Matrix Multiplication polynomials for any arbitrary function .
We also give a dual version of our result for the sum of low-variate ROABPs (read-once oblivious ABPs) and read- oblivious ABPs. Both smABP and ROABP are very well-studied ‘simple’ models; our work puts them at the forefront of understanding Valiant’s conjecture.