Computer Science/Discrete Mathematics Seminar I
Lower Bounds for Set-Multilinear Branching Programs
In this talk, I will discuss lower bounds for a certain set-multilinear restriction of algebraic branching programs. The significance of the lower bound and the model is underscored by the recent work of Bhargav, Dwivedi, and Saxena (2023), which showed that super-polynomial lower bounds for the model of sum of ordered set multilinear ABPs -- when the underlying polynomial of sufficiently low degree -- would imply super-polynomial lower bounds against general ABPs, thereby resolving Valiant's longstanding conjecture that the permanent polynomial cannot be computed efficiently by ABPs. We will discuss a recent result which "almost" meets this low-degree demand.
This is based on joint work with Prerona Chatterjee, Deepanshu Kush and Amir Shpilka.