The Complexity of Min-Max Optimization for Quadratic Polynomials
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 13 of its 23 references that are in the map. First posted on arXiv 15 Jun 2026.
Builds on
13 of 23 references.
References · 13
- 2020The Complexity of Constrained Min-Max Optimizationcited by 82
- 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
- 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
- 2020The Complexity of Gradient Descent: CLS = PPAD cap PLScited by 17
- 2022Pure-Circuit: Tight Inapproximability for PPADcited by 7
- 2024Improved Hardness Results for Min-Max Optimization with Coupled Constraintscited by 5
- 2015Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nashcited by 4
- 2023The Complexity of Computing KKT Solutions of Quadratic Programscited by 4
- 2021Subgradient Ellipsoid Method for Nonsmooth Convex Problemscited by 2
- 2025The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Gamescited by 2
- 2026The Complexity of Min-Max Optimization with Product Constraintscited by 2
- 2024The Complexity of Two-Team Polymatrix Games with Independent Adversariescited by 1
1 more
- 2026Min-Max Optimization Requires Exponentially Many Queriescited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.