Towards an algebraic natural proofs barrier via polynomial identity testing
Preprint
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.Keywords
All Related Versions
This publication has 42 references indexed in Scilit:
- Geometric complexity theory and matrix poweringDifferential Geometry and its Applications, 2017
- Geometric complexity theory V: Efficient algorithms for Noether normalizationJournal of the American Mathematical Society, 2016
- Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanincomputational complexity, 2016
- Lower Bounds for Sums of Powers of Low Degree Univariates2015
- Unifying Known Lower Bounds via Geometric Complexity Theorycomputational complexity, 2015
- Improved bounds for reduction to depth 4 and depth 3Information and Computation, 2015
- Improved Bounds for Reduction to Depth 4 and Depth 32013
- Arithmetic circuits: The chasm at depth four gets widerTheoretical Computer Science, 2012
- Proving Lower Bounds Via Pseudo-random Generators2005
- Natural ProofsJournal of Computer and System Sciences, 1997