- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- The Surprising Power of Constant Depth Algebraic Proofs
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
The Surprising Power of Constant Depth Algebraic Proofs Mouli, Sasank
Description
A major open problem in proof complexity is to prove super-polynomial lower bounds for $AC^0[p]$-Frege proofs. This system is the analog of $AC^0[p]$, the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), there are no significant lower bounds for $AC^0[p]$-Frege. Significant and extensive *degree* lower bounds have been obtained for a variety of subsystems of $AC^0[p]$-Frege, including Nullstellensatz (Beame et. al. '94), Polynomial Calculus (Clegg et. al. '96), and SOS (Griegoriev and Vorobjov, '01). However to date there has been no progress on $AC^0[p]$-Frege lower bounds. In this paper we study constant-depth extensions of the Polynomial Calculus introduced by Griegoriev and Hirsch, '03. We show that these extensions are much more powerful than was previously known. Our main result is that small depth Polynomial Calculus (over a sufficiently large field) can polynomially simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams and Sum-of-Squares, and they can also quasi-polynomially simulate $AC^0[p]$-Frege as well as $TC^0$-Frege. Thus, proving strong lower bounds for $AC^0[p]$-Frege would seem to require proving lower bounds for systems as strong as $TC^0$-Frege.
Item Metadata
| Title |
The Surprising Power of Constant Depth Algebraic Proofs
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2020-01-21T17:03
|
| Description |
A major open problem in proof complexity is to prove super-polynomial lower bounds for $AC^0[p]$-Frege proofs. This system is the analog of $AC^0[p]$, the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), there are no significant lower bounds for $AC^0[p]$-Frege. Significant and extensive *degree* lower bounds have been obtained for a variety of subsystems of $AC^0[p]$-Frege, including Nullstellensatz (Beame et. al. '94), Polynomial Calculus (Clegg et. al. '96), and SOS (Griegoriev and Vorobjov, '01). However to date there has been no progress on $AC^0[p]$-Frege lower bounds.
In this paper we study constant-depth extensions of the Polynomial Calculus introduced by Griegoriev and Hirsch, '03. We show that these extensions are much more powerful than was previously known. Our main result is that small depth Polynomial Calculus (over a sufficiently large field) can polynomially simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams and Sum-of-Squares, and they can also quasi-polynomially simulate $AC^0[p]$-Frege as well as $TC^0$-Frege. Thus, proving strong lower bounds for $AC^0[p]$-Frege would seem to require proving lower bounds for systems as strong as $TC^0$-Frege.
|
| Extent |
28.0 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: UC San Diego
|
| Series | |
| Date Available |
2020-07-20
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0392462
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Graduate
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International