The Complexity of Min-Max Optimization for Quadratic Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alexandros Hollender
cs.CC cs.GT cs.LG math.OC
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.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.