Title | ||
---|---|---|
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors |
Abstract | ||
---|---|---|
We say that a polynomial f(x
1,...,x
n
) is indecomposable if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The polynomial decomposition problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that for multilinear
polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint.
In this paper we show that the problem of derandomizing polynomial identity testing is essentially equivalent to the problem
of derandomizing algorithms for polynomial decomposition. More accurately, we show that for any reasonable circuit class there
is a deterministic polynomial time (black-box) algorithm for polynomial identity testing of that class if and only if there
is a deterministic polynomial time (black-box) algorithm for factoring a polynomial, computed in the class, to its indecomposable
components.
An immediate corollary is that polynomial identity testing and polynomial factorization are equivalent (up to a polynomial
overhead) for multilinear polynomials. In addition, we observe that derandomizing the polynomial decomposition problem is
equivalent, in the sense of Kabanets and Impagliazzo [1], to proving arithmetic circuit lower bounds for NEXP.
Our approach uses ideas from [2], that showed that the polynomial identity testing problem for a circuit class C\mathcal C is essentially equivalent to the problem of deciding whether a circuit from C\mathcal C computes a polynomial that has a read-once arithmetic formula.
|
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-14165-2_35 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
deterministic polynomial time,polynomial overhead,polynomial identity testing problem,polynomial decomposition problem,variable disjoint factor,polynomial factorization,arithmetic circuit lower bound,polynomial identity testing,multilinear polynomial,circuit class c,polynomial decomposition,lower bound,polynomial time | Alternating polynomial,Discrete mathematics,Polynomial identity testing,Stable polynomial,Combinatorics,Monic polynomial,Reciprocal polynomial,Matrix polynomial,Symmetric polynomial,Factorization of polynomials,Mathematics | Journal |
Volume | ISSN | ISBN |
17 | 0302-9743 | 3-642-14164-1 |
Citations | PageRank | References |
21 | 0.92 | 32 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir Shpilka | 1 | 1095 | 64.27 |
Ilya Volkovich | 2 | 145 | 8.64 |