The Complexity of Min-Max Optimization for Quadratic Polynomials

• URL: http://arxiv.org/abs/2606.17000v1
• Date: Mon, 15 Jun 2026 17:37:13 GMT
• Title: The Complexity of Min-Max Optimization for Quadratic Polynomials
• Abstract summary: We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratics.<n>As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix.
• Score: 71.85811744604827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Nearly optimal polynomial approximations for the quantum singular value transform [0.0]
  We introduce approximations of the even and odd step functions on the interval $[-1,$] with simple Chebyshev coefficients.<n>We derive rigorous error bounds that are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor.
  arXiv  Detail & Related papers  (2026-07-13T22:18:53Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  Solving variational inequalities (SVIs) is a foundational problem at the heart of optimization.<n>Most research has focused on carving out specific subclasses that elude those intractability barriers.
  arXiv  Detail & Related papers  (2025-04-04T13:24:41Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Accelerated and Improved Stabilization for High Order Moments of Racah Polynomials [0.6445605125467573]
  We propose a new algorithm for the computation of Racahs called Improved Stabilization (ImSt) ImSt works for wider range of parameters until higher degree than the current algorithms.
  arXiv  Detail & Related papers  (2022-12-30T17:07:26Z)
• Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
  Max-pooling layers are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride.
  arXiv  Detail & Related papers  (2022-09-29T17:45:54Z)
• Progressive approximation of bound states by finite series of square-integrable functions [0.0]
  We use the "tridiagonal representation approach" to solve the time-independent Schr"odinger equation for bound states in a basis set of finite size.
  arXiv  Detail & Related papers  (2022-02-20T00:25:35Z)
• Sums of Separable and Quadratic Polynomials [0.3222802562733786]
  We study separable plus quadratic (SPQ)s. We show that convex SPQ optimization problems can be solved by "small" semidefinite programs.
  arXiv  Detail & Related papers  (2021-05-11T03:26:46Z)
• Complexity Aspects of Fundamental Questions in Polynomial Optimization [3.42658286826597]
  We show that unless P=NP, there cannot be a SDP that finds a point within Euclidean distance of a local minimum of a quadratic program. We also show that testing whether aally constrained program with a finite optimal value has an optimal solution is NP-hard. In our final chapter, we present an characterization of coercives that lends itself to a hierarchy of SDPs.
  arXiv  Detail & Related papers  (2020-08-27T14:58:02Z)
• Complexity aspects of local minima and related notions [3.42658286826597]
  We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariates. We show that it is strongly NP-hard to decide if a cubic has a critical point. We briefly present a potential application of finding local minima cubics to the design of a third-order Newton method.
  arXiv  Detail & Related papers  (2020-08-14T00:50:13Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.