In this talk, we will discuss new lower bounds for the model of sum of ordered set-multilinear algebraic branching programs. The significance of these lower bounds is underscored by the recent work of Bhargav, Dwivedi, and Saxena (2023), which showed that super-polynomial lower bounds against this model -- for a set-multilinear 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 our new results which "almost" meet this low-degree demand. This is joint work with Prerona Chatterjee, Shubhangi Saraf, and Amir Shpilka.
Short Bio:
Deepanshu Kush is a fourth year PhD student in Computer Science at the University of Toronto, where he is advised by Shubhangi Saraf. His research interests are broadly in theoretical computer science and related areas of math with a focus on computational complexity theory.
