Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

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