[Colloquium] U of C - CS Theory Seminar - Tuesday, December 3, 2024

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Michael A. Forbes
University of Illinois at Urbana-Champaign

 [Michael A. Forbes]

Tuesday, December 3, 2024 at 3:30pm
Kent Chemical Laboratory, Room 102


Title: Low-Depth Algebraic Circuit Lower Bounds over Any Field

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 super polynomial 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-Mult linearization result of LST with a set-Mult linearization that works over any field, by using the Binet-Minc identity.


Bio: Michael A. Forbes obtained his Ph. D. in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology in 2014, where he was co-advised by Scott Aaronson and Amir Shpilka. In his dissertation, he developed new deterministic algorithms to solve cases of the Polynomial Identity Testing problem. In 2017, he joined the faculty of the University of Illinois at Urbana-Champaign. His research focuses on the interaction of randomness, algebra, and computation.






Host: Alexander Razborov


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241127/2751a625/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 11489 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241127/2751a625/attachment-0001.jpg>