A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials

Abstract

We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set $H\subseteq {\mathbb{R}}_{\ge 0}^n$, we construct an $\hat{I}\mu$-Cover of the joint value set $\{(f_1(x),\dots ,f_m(x)):x\in H\}$ in the ${\ell }_{\infty }$-norm. This cover is of size $n^{O(\log (mn)/\hat{I}{\mu }^2)}$, provided the polynomials have constant range over the smallest ${\ell }_1$-ball inscribing $H$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest ${\ell }_1$-ball containing $H$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to $H$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.

Topics & keywords