Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-063 | 8th January 2021 08:57

On the Existence of Algebraically Natural Proofs

RSS-Feed




Revision #1
Authors: Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse
Accepted on: 8th January 2021 08:57
Downloads: 307
Keywords: 


Abstract:

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n variate polynomial of degree at most n^c with bounded integer coefficients and for N = \binom{n^c + n}{n}, P_{N,c} \emph{vanishes} on the coefficient vector of f_n.
* There exists a family {h_n} of polynomials where h_n is an n variate polynomial of degree at most n^c with bounded integer coefficients such that for N = \binom{n^c + n}{n}, P_{N,c} \emph{does not vanish} on the coefficient vector of h_n.

In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients.
In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence \emph{against} a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017).

Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes. Our proofs also extend to finite fields of small size.



Changes to previous version:

Incorporating some comments on the previous version.
* We now use the phrase 'equations for a class' instead of 'defining equations'.
* Main theorem for VP now uses the result of Heintz and Schnorr (1980).


Paper:

TR20-063 | 29th April 2020 14:54

On the Existence of Algebraically Natural Proofs


Abstract:

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n variate polynomial of degree at most n^c with bounded integer coefficients and for N = \binom{n^c + n}{n}, P_{N,c} -vanishes- on the coefficient vector of f_n.
* There exists a family {h_n} of polynomials where h_n is an n variate polynomial of degree at most n^c with bounded integer coefficients such that for N = \binom{n^c + n}{n}, P_{N,c} -does not vanish- on the coefficient vector of h_n.

In other words, there are efficiently computable defining equations for polynomials in VP that have small integer coefficients.
In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence -against- a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017).

Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree defining equations for these classes, and also extend to finite fields of small size.



ISSN 1433-8092 | Imprint