Seminar • Algorithms and Complexity • New Lower Bounds for Set Multilinear Formulas

Please note: This seminar will take place in DC 1304 and online.

Shubhangi Saraf, Associate Professor
Department of Mathematics, Department of Computer Science, University of Toronto

The recent exciting breakthrough by Limaye, Srinivasan, and Tavenas showing superpolynomial lower bounds for constant-depth algebraic circuits has underscored the importance of studying the complexity of set multilinear formulas.

In this talk, along with discussing the impact of this work and several others in the literature, I will discuss some new results in this area, namely strong (and “sharp”) lower bounds for set-multilinear circuits/formulas in the constant (or low) depth setting.

This is based on joint work with Deepanshu Kush.