The Complexity of Min-Max Optimization for Quadratic Polynomials
2026-06-15 • Computational Complexity
Computational ComplexityComputer Science and Game TheoryMachine Learning
AI summaryⓘ
The authors show that finding even an approximate balance point (stationary point) in certain game-like math problems that involve both minimizing and maximizing a quadratic function is very hard — in a technical sense called PPAD-hard. This difficulty remains even when the problem is simplified to having variables with limited interaction (each appears in at most three terms). Because of this, they also identify these hard cases in special multiplayer games called two-team zero-sum polymatrix games. Essentially, the authors prove that some natural-looking math problems are computationally tough to solve closely.
PPAD-hardmin-max optimizationstationary pointsquadratic polynomialsmultilinear polynomialsapproximation complexitypolymatrix gamestwo-team zero-sum gamescomputational complexity
Authors
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender
Abstract
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.