pith. sign in

arxiv: 1701.01717 · v1 · pith:N7ELXX5Onew · submitted 2017-01-06 · 💻 cs.CC · math.AG

Towards an algebraic natural proofs barrier via polynomial identity testing

classification 💻 cs.CC math.AG
keywords algebraicbarriercomplexitylowernaturalproofsboundscircuit
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.