[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 is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign, in particular he is a member of the Theory Group.  He also studies the theory of computation (complexity theory), and more particularly 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/20241125/46c32b53/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/20241125/46c32b53/attachment-0001.jpg>