Paper Info
Title
On the Existence of Algebraically Natural Proofs
Abstract
For every constant , we show that there is a family {PN, 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 {fn} of polynomials in VP, where fn is an n variate polynomial of degree at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sup> with bounded integer coefficients and for N=n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sup> +nn, PN, c vanishes on the coefficient vector of fn. There exists a family {hn} of polynomials where hn is an n variate polynomial of degree at most n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sup> with bounded integer coefficients such that for N=n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</sup> +nn, PN, c does not vanish on the coefficient vector of hn. 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 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 [1], and Grochow, Kumar, Saks and Saraf [2]. 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 and also extend to finite fields of small size. 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 and also extend to finite fields of small size.
Year
DOI
Venue
2020
10.1109/FOCS46700.2020.00085
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
Volume
Computational Complexity,Algebraic Complexity,Algebraically Natural Proofs,Lower Bounds
Conference
27
ISSN
ISBN
Citations 
1523-8288
978-1-7281-9622-0
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Chatterjee Prerona100.34
Mrinal Kumar2377.11
Ramya C.300.34
Ramprasad Saptharishi418413.72
Tengse Anamay500.34