Introduction
Optimization over the boolean hypercube $\{0, 1\}^n$ is a fundamental challenge in theoretical computer science, underpinning landmark NP-hard problems such as Max-Cut and the Independent Set problem. To address these, researchers typically employ hierarchies of convex relaxations. For decades, the Sums of Squares (SOS) hierarchy has been the standard approach, certifying nonnegativity by decomposing polynomials into squared components. However, SOS faces significant hurdles, including high-degree requirements for certain problems (e.g., the Knapsack Problem) and the substantial numerical complexity of Semidefinite Programming (SDP) solvers.
This research investigates Sums of Nonnegative Circuit Polynomials (SONC) as a robust alternative to SOS for hypercube optimization. The authors demonstrate that SONC achieves theoretical parity with SOS in key benchmarks while offering distinct algebraic properties that may overcome traditional SOS limitations.
Methodology: The SONC Framework
Unlike the SOS approach, which is rooted in the principle that squares are inherently nonnegative, the SONC framework leverages the Arithmetic-Geometric Mean (AM-GM) inequality.
A "circuit polynomial" is a sparse polynomial whose nonnegativity is efficiently verifiable via a "circuit number." A SONC is a sum of these fundamental units. By utilizing tools from algebraic geometry—specifically Gröbner bases and Newton polytopes—the authors prove that any polynomial nonnegative on the boolean hypercube can be represented as a SONC. Furthermore, they apply Carathéodory’s Theorem to establish the existence of sparse certificates, which is critical for computational efficiency.
Key Theoretical Insights
The paper reveals several critical properties of the SONC cone in the context of the hypercube:
- Theoretical Parity with SOS: The authors establish that for a polynomial of degree $d$ nonnegative over a hypercube, a SONC certificate of degree at most $n+d$ always exists. This mirrors the completeness results known for SOS.
- Lack of Affine Invariance: A significant finding is that the SONC cone is not invariant under affine transformations. Unlike SOS, where a coordinate shift or scaling preserves the certificate's structure, SONC certificates can become significantly more complex under such changes. This "brittleness" highlights a fundamental structural difference between the two methods.
- Sparsity and "Short" Certificates: The research proves that if a degree $d$ SONC certificate exists, there is a version containing at most $n^{O(d)}$ terms. This suggests SONC is particularly well-suited for high-dimensional problems with local or low-degree interactions.
- Absence of a Putinar-type Shortcut: In SOS theory, Putinar’s Positivstellensatz provides simplified representations under specific conditions. The authors demonstrate that a direct SONC equivalent does not exist, further distinguishing the two algebraic frameworks.
Results and Computational Complexity
The study provides concrete bounds on the existence and complexity of SONC certificates:
- Existence Bound: Every $n$-variate polynomial nonnegative on the boolean hypercube has a SONC certificate of degree at most $n$.
- Complexity Bound: Identifying a degree $d$ SONC certificate can be reduced to a Relative Entropy Program (REP). While REPs are convex and generally efficient, the existence of certificates with only $n^{O(d)}$ circuit polynomials provides a theoretical upper bound on proof size.
- Structural Boundaries: Through explicit constructions, the authors map the boundaries of SONC, identifying polynomials that are nonnegative but fail to meet simplified SONC criteria.
Conclusion and Future Directions
While the authors prove the existence of short SONC certificates, the algorithmic challenge of efficiently locating them within the vast space of circuit polynomials remains. Future research is directed toward:
- Developing algorithms to identify "SONC-friendly" affine transformations.
- Empirical testing on combinatorial problems where SOS is known to be inefficient, such as the Knapsack or Planted Clique problems.
- Extending these results from the boolean hypercube to more general finite varieties.
Summary updated