On the Existence of Algebraically Natural Proofs

The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the efficacy of commonly used techniques for proving lower bounds in algebraic complexity. We use the known connections between algebraic hardness and pseudorandomness to shed some more light on the question relating to this framework, as follows.

• The subclass of VP that contains polynomial families with bounded coefficients, has efficient equations. Over finite fields, this result holds without any restriction on coefficients. Further, both these results extend to any class that admits a low-variate, low-degree universal map: a generator for all polynomials in the class. Most well-studied classes have this property, e.g. VNP, VBP, VF.

• Over fields of characteristic zero, VNP does not have any efficient equations, if the Permanent is exponentially hard for algebraic circuits. Moreover, exponential hardness of the Permanent in the approximative sense, even rules out efficient equations of large degree. This gives the only known barrier to "natural" lower bound techniques (that follows from believable hardness assumptions), and also shows that the restriction on coefficients in the first category of results about VNP is necessary.

The first set of results is obtained by algebraizing the well-known method of generating hardness from non-trivial hitting sets, and by generalizing the result of Heintz and Schnorr (1980) that proves the existence of hitting sets for VP. The conditional hardness of equations for VNP uses the fact that pseudorandomness against a class can be extracted from a polynomial that is (sufficiently) hard for that class (Kabanets and Impagliazzo, 2004).

• This paper builds on a combination of two preliminary works, titled "On the Existence of Algebraically Natural Proofs" (FOCS 2020) and "If VNP is hard, then so are equations for it" (STACS 2022).

†