Sum-of-squares optimization becomes polynomial-time on Boolean problems
Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains
Data Structures and Algorithms
Summary
Finding exact proofs that certain Boolean polynomial inequalities hold is usually very hard. The authors studied a new way to organize the polynomial equations involved, called vanishing ideals, which allows for simpler and faster verification of these proofs using sum-of-squares techniques. Their method ensures that optimized solutions can be found in polynomial time with rational values, making verification more practical for certain classes of problems. This approach can handle both minimization and maximization problems that have special Boolean structure, expanding the scope of efficient proof finding.
What this means in practice
- •For optimization software developers: Implement more efficient sum-of-squares solvers that run in polynomial time with exact rational outputs on Boolean polynomial problems with min-closed or max-closed structures.
- •For constraint programming engineers: Help certify feasibility or infeasibility of Boolean linear constraints using polynomial-time sum-of-squares proof constructions with controlled degree and coefficients.
A theory result. No direct application yet.
Authors
Monaldo Mastrolilli
Abstract
Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over Boolean polynomial systems. A complete, constructible identity space gives an augmented moment SDP that can be optimized with exact rational feasibility and arbitrary additive accuracy. We give a self-contained geometric implementation: an explicit affine reduction and a simplex of Boolean evaluations supply the radius bounds required by rational ellipsoids. The identity space can be constructed directly or extracted from a supplied graded Groebner basis, including one supplied at a higher truncation degree. An explicit transfer theorem connects this augmented formulation to the original system. Two-sided SoS derivations eliminate the added equality axioms from certificates, with controlled degree and coefficient growth, and imply containment of a projected higher-level moment relaxation in the augmented body. Together with spectral coefficient bounds, this gives polynomial-time search for rational proofs with an additive perturbation. For Min-closed linear systems, propagation constructs the identity space in polynomial time at fixed degree and gives degree-(4t+4) certificates for both signs of each degree-t basis element. Consequently, a rational degree-(8d+4) proof of f + epsilon >= 0 can be found in polynomial time for fixed d whenever f >= 0 has a degree-2d proof. The augmented degree-2d moment SDP can be optimized in polynomial time with exact rational feasibility and a comparison to the original degree-(8d+4) relaxation. Boolean complementation gives the same results for Max-closed systems, including generalized packing and covering. Min-closed systems thus provide a concrete application of the general criteria. All complexity bounds are in the Turing model.