Towards an algebraic natural proofs barrier via polynomial identity testing
read the original abstract
We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier
Establishes an unconditional AC0-natural-proofs barrier limiting such proofs to lower bounds of at most 2^{n^{7/(d-5)}} for depth-d circuits via a localized Trevisan-Xue PRG.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.