ECCC-Report TR10-114https://eccc.weizmann.ac.il/report/2010/114Comments and Revisions published for TR10-114en-usSun, 18 Jul 2010 02:15:13 +0300
Paper TR10-114
| The Complexity of Testing Monomials in Multivariate Polynomials |
Zhixiang Chen,
Bin Fu
https://eccc.weizmann.ac.il/report/2010/114The work in this paper is to initiate a theory of testing
monomials in multivariate polynomials. The central question is to
ask whether a polynomial represented by certain economically
compact structure has a multilinear monomial in its sum-product
expansion. The complexity aspects of this problem and its variants
are investigated with two folds of objectives. One is to
understand how this problem relates to critical problems in
complexity, and if so to what extent. The other is to exploit
possibilities of applying algebraic properties of polynomials to
the study of those problems. A series of results about
$\Pi\Sigma\Pi$ and $\Pi\Sigma$ polynomials are obtained in this
paper, laying a basis for further study along this line.Sun, 18 Jul 2010 02:15:13 +0300https://eccc.weizmann.ac.il/report/2010/114