Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-039 | 25th March 2020 20:57

#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

TR20-039
Authors: Pranjal Dutta, Nitin Saxena, Thomas Thierauf
Publication: 25th March 2020 23:21
Keywords:

Abstract:

We 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.

ISSN 1433-8092 | Imprint