# The Complexity of Min-Max Optimization for Quadratic Polynomials

arXiv: https://arxiv.org/abs/2606.17000 · HTML: https://mlsanity.com/paper/2606.17000/

## Key facts

- Cited by 1 papers 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 (most cited first, 13 of 13)

- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Pure-Circuit: Tight Inapproximability for PPAD](https://mlsanity.com/paper/2209.15149/) (2022)
- [Improved Hardness Results for Min-Max Optimization with Coupled Constraints](https://mlsanity.com/paper/2411.03248/) (2024)
- [Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash](https://mlsanity.com/paper/1504.02411/) (2015)
- [The Complexity of Computing KKT Solutions of Quadratic Programs](https://mlsanity.com/paper/2311.13738/) (2023)
- [Subgradient Ellipsoid Method for Nonsmooth Convex Problems](https://mlsanity.com/paper/2106.13340/) (2021)
- [The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games](https://mlsanity.com/paper/2502.08519/) (2025)
- [The Complexity of Min-Max Optimization with Product Constraints](https://mlsanity.com/paper/2602.04665/) (2026)
- [The Complexity of Two-Team Polymatrix Games with Independent Adversaries](https://mlsanity.com/paper/2409.07398/) (2024)
- [Min-Max Optimization Requires Exponentially Many Queries](https://mlsanity.com/paper/2605.13806/) (2026)

## Built on by (most cited first, 1 of 1)

- [Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games](https://mlsanity.com/paper/2610.07814/) (2026)

## 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.