cs.CCJun 15, 2026

The Complexity of Min-Max Optimization for Quadratic Polynomials

Authors: Martino BernasconiMatteo CastiglioniAndrea CelliAlexandros Hollender

Organizations: Bocconi University · Politecnico di Milano · University of Oxford

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.

Explore similar work

CardsList
  1. Min-Max Optimization Requires Exponentially Many Queries

    May 13, 2026Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1Convex OptimizationNonconvex