Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-114 | 17th July 2010 23:06

The Complexity of Testing Monomials in Multivariate Polynomials


Authors: Zhixiang Chen, Bin Fu
Publication: 18th July 2010 02:15
Downloads: 1691


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

ISSN 1433-8092 | Imprint