Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

Abstract

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^{\ast }(3^{n}s(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^{\ast }(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\ne NP$; and a higher $1.0604$ lower bound, assuming the Unique Games Conjecture.

References in corpus (2)

• Finding paths of length k in O*(2^k) time
• Algorithms for Testing Monomials in Multivariate Polynomials

Cited by in corpus (3)

• Faster Deterministic Algorithms for Packing, Matching and $t$-Dominating Set Problems
• Monomial Testing and Applications
• Towards Randomized Testing of $q$-Monomials in Multivariate Polynomials