Introduction
In the field of computational complexity, the representation of multivariate polynomials plays a critical role in determining the feasibility of extracting specific algebraic information. While a polynomial can be written in an expanded sum-of-monomials form, it is often more efficient to represent it compactly using arithmetic circuits or specific structural forms such as $\Pi\Sigma\Pi$ (a product of sums of products). However, this compactness introduces significant computational challenges. This paper investigates the complexity of identifying and approximating multilinear monomials—terms where each variable appears with an exponent of at most one—within these compact representations.
Problem Formulation
The authors focus on two primary computational problems related to multilinear monomials:
- The Coefficient Problem: Given a polynomial $P(x_1, \dots, x_n)$ and a specific multilinear monomial, determine its coefficient. In expanded form, this is trivial; however, in compact forms like arithmetic circuits, the expansion can be exponentially large.
- The Maximum Multilinear Monomial (Max-MLM) Problem: Identify the "longest" multilinear monomial (the one containing the greatest number of distinct variables) that exists within the polynomial's expansion.
These problems are not merely theoretical; they serve as algebraic generalizations of fundamental combinatorial problems, including the $k$-path problem in graphs, the Satisfiability problem (SAT), and the computation of the permanent of a matrix.
Algorithmic Approaches and Results
The paper provides a comprehensive analysis of the algorithmic landscape, identifying both the limits of computation and specific cases where efficient approximation is possible.
Exact Algorithms
For general arithmetic circuits of size $s(n)$, the authors propose a bottom-up evaluation algorithm that tracks multilinear terms at each gate. This approach yields a time complexity of $O^*(3^n s(n))$. For the more specific $\Pi\Sigma\Pi$ structure, they refine this to $O^*(2^n)$, a result that notably matches Ryser’s formula—the best-known deterministic bound for computing the permanent of a matrix. This alignment reinforces the deep connection between multilinear monomial detection and the counting of perfect matchings.
Approximation Schemes
A significant contribution of the work is the development of a Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for $\Pi\Sigma$ polynomials (products of linear sums). By reducing the coefficient problem in $\Pi\Sigma$ polynomials to the problem of counting perfect matchings in bipartite graphs, the authors leverage existing randomized algorithms to provide efficient approximations where exact solutions are #P-hard.
Complexity and Inapproximability
The research establishes a sharp "phase transition" in complexity based on the polynomial's structure. While $\Pi\Sigma$ polynomials allow for approximation, the introduction of even degree-2 terms (e.g., $x_i x_j$) in a $\Pi\Sigma\Pi$ structure renders the problem not only #P-hard to solve exactly but also impossible to approximate within any constant factor, assuming $P \neq NP$.
Hardness of Max-MLM
The Max-MLM problem is shown to be a generalization of the Maximum Independent Set problem, one of the most notoriously difficult problems in graph theory. Consequently, the authors prove strict lower bounds on approximation:
- For general $\Pi\Sigma\Pi$ polynomials, the approximation factor is bounded by $n^{(1-\epsilon)/2}$.
- For degree-2 $\Pi\Sigma\Pi$ polynomials, the lower bound is 1.0476 (assuming $P \neq NP$) and 1.0604 (under the Unique Games Conjecture).
Conclusion
This paper delineates the boundaries of what is computationally possible when dealing with multilinear monomials in compact polynomial representations. By linking algebraic problems to graph-theoretic constants like matchings and independent sets, the authors provide a robust framework for understanding the hardness of these tasks. The gap between the greedy algorithm's approximation factor (2) and the proven lower bounds for degree-2 polynomials remains an open area for future research, as does the exploration of approximation schemes for broader classes of polynomial structures beyond the $\Pi\Sigma$ restriction.
Summary updated