Computer Science Seminar
Speaker: Bhargav CS, IIT Kanpur
Date: Friday, 3 November 2023
Time: 3.30 PM
Venue: Lecture Hall 6
Lower bounds for the sum of small-size algebraic branching programs
Bhargav CS
IIT Kanpur.
03-11-23

---

Abstract

In this talk we show that proving 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 poly(n) ABPs, each of size (:= number of vertices) n^{o(1)}, cannot compute the family of Iterated Matrix Multiplication polynomials 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). Both smABP and ROABP are very well-studied 'simple' models; our work puts them at the forefront of understanding Valiant's conjecture.