Improved Low-Depth Set-Multilinear Circuit Lower Bounds

Deepanshu Kush, Shubhangi Saraf

We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over…