Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polynomial factorization:
TR14-001 | 4th January 2014
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

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

ISSN 1433-8092 | Imprint