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
- steidin2@illinois.edu
- Views
- 54
- Originating Calendar
- Siebel School 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).