Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-001 | 4th January 2014 10:45

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization


Authors: Swastik Kopparty, Shubhangi Saraf, Amir Shpilka
Publication: 4th January 2014 10:47
Downloads: 4745


In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors of $f$ can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of $f$).

Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.

Previously, such an equivalence was known only for multilinear circuits (Shpilka and Volkovich, ICALP 2010).

ISSN 1433-8092 | Imprint