Grainger College of Engineering, All Events

View Full Calendar

Michael A. Forbes "Low-depth algebraic circuit lower bounds over any field"

Event Type
Seminar/Symposium
Sponsor
Illinois Computer Science
Location
3401 Siebel Center for Computer Science
Date
Nov 27, 2023   10:00 am  
Speaker
Michael A. Forbes (UIUC)
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Views
12
Originating Calendar
Computer Science Speakers Calendar

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).

link for robots only