Theory of Computing
-------------------
Title     : Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits
Authors   : Michael A. Forbes, Amir Shpilka, and Ben Lee Volk
Volume    : 14
Number    : 18
Pages     : 1-45
URL       : https://theoryofcomputing.org/articles/v014a018

Abstract
--------

We formalize a framework of _algebraically natural_ lower bounds for
algebraic circuits. Just as with the natural proofs notion of Razborov
and Rudich (1997) for Boolean circuit lower bounds, our notion of
algebraically natural lower bounds captures nearly all lower bound
techniques known. However, unlike in the Boolean setting, there has
been no concrete evidence demonstrating that this is a _barrier_ to
obtaining super-polynomial lower bounds for general algebraic
circuits, as there is little understanding whether algebraic circuits
are expressive enough to support "cryptography" secure against
algebraic circuits.

Following a similar result of Williams (2016) in the Boolean setting,
we show that the existence of an algebraic natural proofs barrier is
_equivalent_ to the existence of _succinct_ derandomization of the
polynomial identity testing problem, that is, to the existence of a
hitting set for the class of $\poly(N)$-degree $\poly(N)$-size
circuits which consists of coefficient vectors of polynomials of
$\polylog(N)$ degree with $\polylog(N)$-size circuits. Further, we
give an explicit universal construction showing that _if_ such a
succinct hitting set exists, then our universal construction suffices.

Further, we assess the existing literature constructing hitting sets
for restricted classes of algebraic circuits and observe that _none_
of them are succinct as given. Yet, we show how to modify some of
these constructions to obtain succinct hitting sets. This constitutes
the first evidence supporting the existence of an algebraic natural
proofs barrier.

Our framework is similar to the Geometric Complexity Theory (GCT)
program of Mulmuley and Sohoni (2001), except that here we emphasize
constructiveness of the proofs while the GCT program emphasizes
symmetry. Nevertheless, our succinct hitting sets have relevance to
the GCT program as they imply lower bounds for the complexity of the
defining equations of polynomials computed by small circuits.