New framework solves polynomial optimization in quasi-polynomial time

A team of computer scientists has unveiled a powerful mathematical framework that tackles a broad class of optimization problems with polynomial constraints. The paper, authored by Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina, develops a method to approximate the joint values of any set of constant-degree polynomials over a convex set. They construct a quasi-polynomial-sized ε-cover—a set of points that approximates all possible outputs within a small error bound. The cover size scales as n^{O(log(mn)/ε^2)}, where n is the dimension and m the number of polynomials, provided the polynomials have bounded range on the smallest ℓ₁-ball containing the set. The construction uses a two-step scheme: first, a probabilistic argument via Bernstein approximation produces a pre-cover on the ℓ₁-ball; second, recursive degree reduction and feasibility programs compress it to the target convex set. This approach generalizes classic net-based sparsifications for linear functions to arbitrary constant-degree polynomial families.

The existence of such covers immediately yields Quasi-Polynomial Time Approximation Schemes (QPTAS) for multiple fundamental problems. These include fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games (a model in computational game theory), variational inequalities with polynomial operators (which imply guarantees for local Nash equilibria in polynomial games), and additive approximation for the normalized densest k-subhypergraph on hypergraphs of constant uniformity. The work bridges algorithmic game theory, combinatorial optimization, and convex geometry. For professionals in AI and operations research, this framework promises near-optimal solutions for previously intractable optimization landscapes, running in time only slightly worse than polynomial.