[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

Michael A. Forbes
University of Illinois at Urbana-Champaign
 
 
  
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241126/31ecab47/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 11489 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241126/31ecab47/attachment.jpg>