文章基本信息

标题：Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT
本地全文：下载
作者：Pranjal Dutta ; Nitin Saxena ; Thomas Thierauf 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-35
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the univariate polynomial fd := (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 Ω(d) for fd . 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 fd implies blackbox-PIT in P. Assuming the Generalized Riemann Hypothesis (GRH), it also implies VP 6= 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 25th-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.