{"id":"arxiv/2606.17000","url":"https://arxiv.org/abs/2606.17000","tags":["cs.CC","cs.GT","cs.LG","math.OC"],"score":0,"title":"The Complexity of Min-Max Optimization for Quadratic Polynomials","domain":"cs.CC","source":"arxiv","authors":["Martino Bernasconi","Matteo Castiglioni","Andrea Celli","Alexandros Hollender"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}