Equivalence of polynomial identity testing and polynomial factorization (Q2351391): Difference between revisions

In this research paper it is demonstrated that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. More specifically, it is explored that, given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial \(f\), 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. 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.