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.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

    cs.CC 2026-06 unverdicted novelty 7.0

    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.