The Complexity of Min-Max Optimization with Product Constraints

Martino Bernasconi ( Bocconi University )

Local min-max points are a basic notion in min-max optimization. In this talk, I will study the problem of computing approximate local min-max points over the hypercube. I will show that this problem is PPAD-complete, and thus unlikely to have polynomial time algorithms.

The proof builds on recent techniques in PPAD-hardness including the pure-circuit problem of Deligkas, Fearnley, Hollender, and Melissourgos (JACM, 2024) and the idea of hiding incorrect solutions of a problem within another problem which was used in the proof of CLS = PPAD ∩ PLS by Fearnley, Goldberg, Hollender, and Savani (JACM, 2022).

This talk is based on a joint work with Matteo Castiglioni.