Cover Image

Min-Max Optimization Requires Exponentially Many Queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bernasconi, Martino, Castiglioni, Matteo, Celli, Andrea, Hollender, Alexandros
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity Computer Science and Game Theory Machine Learning Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
by: Bernasconi, Martino, et al.
Published: (2024)

The Complexity of Min-Max Optimization with Product Constraints
by: Bernasconi, Martino, et al.
Published: (2026)

Online Fair Allocation with Best-of-Many-Worlds Guarantees
by: Yang, Zongjun, et al.
Published: (2024)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
by: Chen, Xi, et al.
Published: (2024)

The Min Max Average Cycle Weight Problem
by: Elmalem, Noga Klein, et al.
Published: (2025)

Robust Optimality of Bundling Goods Beyond Finite Variance
by: van Eck, Tim S. G., et al.
Published: (2025)

Revenue Maximization in Choice-Based Matching Markets
by: Nissim, Dan, et al.
Published: (2024)

Solving Matrix Games with Near-Optimal Matvec Complexity
by: Karmarkar, Ishani, et al.
Published: (2026)

Barely Random Algorithms and Collective Metrical Task Systems
by: Cosson, Romain, et al.
Published: (2024)

Solving Zero-Sum Games with Fewer Matrix-Vector Products
by: Karmarkar, Ishani, et al.
Published: (2025)

Sequential Selection with Expirations
by: Xu, Yihua, et al.
Published: (2024)

Fare Zone Assignment on Trees
by: Hoefer, Martin, et al.
Published: (2025)

Online Proportional Apportionment
by: Cembrano, Javier, et al.
Published: (2025)

Algorithmically Fair Maximization of Multiple Submodular Objective Functions
by: Amanatidis, Georgios, et al.
Published: (2024)

On the Correlation Gap of Matroids
by: Husić, Edin, et al.
Published: (2022)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
by: Molina, Mathieu, et al.
Published: (2024)

Hedonic Seat Arrangement Problems
by: Bodlaender, Hans L., et al.
Published: (2020)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
by: Hanaka, Tesshu, et al.
Published: (2024)

The Price of Justified Representation
by: Elkind, Edith, et al.
Published: (2021)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Unravelling Expressive Delegations: Complexity and Normative Analysis
by: Tyrovolas, Giannis, et al.
Published: (2023)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Satisfactory Budget Division
by: Gourvès, Laurent, et al.
Published: (2025)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
by: Kawase, Sota, et al.
Published: (2024)

A Quadratic Lower Bound for Stable Roommates Solvability
by: Rosenbaum, Will
Published: (2025)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
by: Benedek, Márton, et al.
Published: (2023)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
by: Koenemann, Jochen, et al.
Published: (2021)

Nemesis, an Escape Game in Graphs
by: Bergé, Pierre, et al.
Published: (2026)

Complexity of Auctions with Interdependence
by: Loiseau, Patrick, et al.
Published: (2026)

EF1 and EFX Orientations
by: Deligkas, Argyrios, et al.
Published: (2024)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Partitioned Matching Games for International Kidney Exchange
by: Benedek, Márton, et al.
Published: (2023)

Generalized Nash Equilibrium Problems with Mixed-Integer Variables
by: Harks, Tobias, et al.
Published: (2021)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement
by: Bansak, Kirk, et al.
Published: (2024)

Markovian Search with Ex-Ante Constraints: Theory and Applications to Socially Aware Algorithmic Hiring
by: Aminian, Mohammad Reza, et al.
Published: (2025)

A Control-Theoretic Perspective on Optimal High-Order Optimization
by: Lin, Tianyi, et al.
Published: (2019)

Dynamic Debt Swapping in Financial Networks
by: Froese, Henri, et al.
Published: (2023)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
by: Glitzner, Frederik, et al.
Published: (2025)