We look forward to seeing you in person in 3401 Siebel Center for Computer Science.
Abstract: The recent breakthrough of Limaye, Srinivasan and Tavenas (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this result to small-characteristic, which in particular is relevant for an approach to prove superpolynomial AC^0[p]-Frege lower bounds.
In this work, we prove super-polynomial algebraic circuit lower bounds against low-depth algebraic circuits over any field, with the same parameters as LST (or even matching the improved parameters of Bhargav, Dutta, and Saxena).
