Computer Science/Discrete Mathematics Seminar I

Low-Depth Algebraic Circuit Lower Bounds Over Any Field

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⁰[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. We give two proofs. The first is logical, showing that even though the proof of LST naively fails in small characteristic, the proof is sufficiently algebraic that generic transfer results imply the result over characteristic zero implies the result over all fields. Motivated by this indirect proof, we then proceed to give a second constructive proof, replacing the field-dependent set-multilinearization result of LST with a set-multilinearization that works over any field, by using the Binet-Minc identity.
 

Date & Time

February 03, 2025 | 10:30am – 11:30am

Location

Wolfensohn Hall and Remote Access

Speakers

Michael A. Forbes, University of Illinois at Urbana-Champaign