The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.
In this talk, along with discussing the impact of these work and several others in the literature, I will discuss some new results in this area, namely strong and near-optimal lower bounds for set-multilinear circuits/formulas in the constant (or low) depth setting, as well as the unbounded depth setting.
This is based on joint work with Deepanshu Kush.
This video was produced by the University of Warwick as part of the 7th Workshop on Algebraic Complexity Theory (WACT) 2023.
