11

views

0

recommends

- Record: found
- Abstract: found
- Article: found

Preprint

This paper is our third step towards developing a theory of testing monomials
in multivariate polynomials and concentrates on two problems: (1) How to
compute the coefficients of multilinear monomials; and (2) how to find a
maximum multilinear monomial when the input is a \(\Pi\Sigma\Pi\) polynomial. We
first prove that the first problem is \#P-hard and then devise a \(O^*(3^ns(n))\)
upper bound for this problem for any polynomial represented by an arithmetic
circuit of size \(s(n)\). Later, this upper bound is improved to \(O^*(2^n)\) for
\(\Pi\Sigma\Pi\) polynomials. We then design fully polynomial-time randomized
approximation schemes for this problem for \(\Pi\Sigma\) polynomials. On the
negative side, we prove that, even for \(\Pi\Sigma\Pi\) polynomials with terms of
degree \(\le 2\), the first problem cannot be approximated at all for any
approximation factor \(\ge 1\), nor {\em "weakly approximated"} in a much relaxed
setting, unless P=NP. For the second problem, we first give a polynomial time
\(\lambda\)-approximation algorithm for \(\Pi\Sigma\Pi\) polynomials with terms of
degrees no more a constant \(\lambda \ge 2\). On the inapproximability side, we
give a \(n^{(1-\epsilon)/2}\) lower bound, for any \(\epsilon >0,\) on the
approximation factor for \(\Pi\Sigma\Pi\) polynomials. When terms in these
polynomials are constrained to degrees \(\le 2\), we prove a \(1.0476\) lower
bound, assuming \(P\not=NP\); and a higher \(1.0604\) lower bound, assuming the
Unique Games Conjecture.

http://arxiv.org/licenses/nonexclusive-distrib/1.0/