Name
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. |
Year | Venue | DocType |
|---|---|---|
2017 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
abs/1701.01717 | 2 | 0.36 |
References | Authors | |
27 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joshua A. Grochow | 1 | 138 | 14.90 |
| Mrinal Kumar 0001 | 2 | 64 | 9.94 |
| Michael Saks | 3 | 2595 | 302.11 |
| Shubhangi Saraf | 4 | 263 | 24.55 |