ECCC-Report TR20-039https://eccc.weizmann.ac.il/report/2020/039Comments and Revisions published for TR20-039en-usWed, 25 Mar 2020 23:21:25 +0200
Paper TR20-039
| Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT |
Pranjal Dutta,
Nitin Saxena,
Thomas Thierauf
https://eccc.weizmann.ac.il/report/2020/039We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.
We show a stunning connection of the conjecture to the two main problems in algebraic complexity: Polynomial Identity Testing (PIT) and VP vs VNP. Our conjecture on $f_d$ implies blackbox-PIT in P. Assuming the Generalized Riemann Hypothesis (GRH), it also implies VP $\neq$ VNP. No such connection to PIT, from lower bounds on constant-powers representation of polynomials was known before. We establish that studying the expression of $(x+1)^d$, as the sum of $25^{th}$-powers of univariates, suffices to solve the two major open questions.
In support, we show that our conjecture holds over the integer ring of any number field. We also establish a connection with the well-studied notion of matrix rigidity. Wed, 25 Mar 2020 23:21:25 +0200https://eccc.weizmann.ac.il/report/2020/039