betaFeedback

WorksComputer Science

On the Role of Geometry in Solving Variational Inequalities

Abstract

The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an ℓp\ell_p ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for p=1p = 1 and multi-player polymatrix games for p=∞p = \infty. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over ℓp\ell_p balls across the full range p∈[1,∞]p\in[1,\infty]. First, for any p≠2p\neq 2, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for p=2p=2, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.

Introduction

Variational inequalities (VIs) provide a unifying language for a host of applications in equilibrium computation, constrained optimization, and complementarity problems [20]. In each of these applications, the geometry of the feasible sets plays a prominent role. For example, flow-conservation constraints arise in network routing, product constraints impose independent choices among multiple agents, while global norm constraints can enforce shared resource or capacity limits. Despite the importance of these geometric constraints, their effect on the complexity of VIs is not fully understood beyond a few special cases.

Formally, given a nonempty compact convex set K⊂Rd\mathcal{K} \subset\mathbb{R}^{d} and a continuous operator F ⁣:K→RdF \colon\mathcal{K} \to\mathbb{R}^{d}, the variational inequality problem asks for a point x∈Kx \in\mathcal{K} such that

⟨x−x′,F(x)⟩≥0for every x′∈K.(1)\langle x-x', F(x) \rangle\ge0 \quad\text{for every } x' \in\mathcal{K}. \tag*{(1)}

A solution to this problem always exists [30], as can be established through Brouwer’s fixed-point theorem. This connection also makes VIs closely related to the complexity class PPAD, which captures the computational difficulty of many fundamental fixed-point and equilibrium problems [40]. However, to operationalize this theory, a central algorithmic goal is to compute solutions efficiently under structural conditions, or otherwise delineate fundamental complexity barriers. Both of these directions have proven to be fruitful, engendering a rich literature [34, 36, 37, 15, 12, 16, 9] (Bernasconi and Castiglioni 2026).

In this paper, we examine the effect of geometry on the complexity of solving variational inequalities. The question that drives our research is:

How does the geometry of the constraint set in conjunction with the structure of the operator affect the complexity of variational inequalities?

To answer this, we focus on the problem of solving VIs over an ℓp\ell_p ball for p∈[1,∞]p \in[1,\infty], examining the entire spectrum of parameters. The two extreme cases are by now well understood, going back to celebrated results in the complexity of equilibria. In particular, at p=1p = 1, the problem amounts to equilibrium computation in symmetric bimatrix games [12], a canonical PPAD-complete problem. At p=∞p = \infty, the underlying feasible set is a hypercube, and the independent interval constraints naturally correspond to mixed strategies in two-action polymatrix games. In these games, computing a Nash equilibrium is PPAD-hard even for a constant precision [44] (Bernasconi, Castiglioni, Celli, and Farina 2026). In fact, the hardness results at both endpoints already hold for affine VIs, where the operator takes the form F(x)=Ax+bF(x) = Ax + b.

The fact that computational hardness arises even for affine VIs is particularly noteworthy. A central ingredient in many PPAD-hardness reductions is the simulation of arithmetic and logical operations, often through piecewise polynomials or arithmetic circuits [15, 12, 44, 18]. In contrast, affine operators lack the algebraic expressiveness to implement such operations directly. Thus, hardness for affine VIs demonstrates how the nonlinear behavior needed for such reductions can instead emerge from the interaction between a simple operator and the geometry of the feasible set.

Previous hardness results for p=1p = 1 or p=∞p = \infty, however, rely on the special structure of simplex and box constraints, and do not directly extend to the remaining ℓp\ell_p balls. Among the intermediate values p∈(1,∞)p \in(1,\infty), the Euclidean case p=2p = 2 is particularly natural, motivated by the prevalence of Euclidean norm constraints in optimization and machine learning. Indeed, bounding the Euclidean norm of a parameter vector is perhaps the most common constraint one encounters in many applications [32, 26], making it the natural domain used in classification and gradient-based methods. Recent work by Attias, Dagan, Daskalakis, Yao, and Zampetakis [ [5] further highlights the importance of this domain, motivated in part by learning problems such as generative adversarial networks and multi-agent reinforcement learning. However, their work studies general operators through smoothed analysis and query complexity over the Euclidean ball; it does not characterize the computational complexity of VIs with low-degree polynomial operators. More broadly, a comprehensive understanding of how the complexity of VIs depends on the geometry of ℓp\ell_p balls and the degree of the operator is still lacking. In this paper, we characterize the complexity landscape for affine and quadratic VIs over ℓp\ell_p balls across the entire spectrum p∈[1,∞]p \in[1,\infty].

Our results

For a parameter p≥1p \ge1, or p=∞p = \infty, let Bpd={x∈Rd:∥x∥p≤1}B_p^d = \{x \in\mathbb{R}^d : \lVert x\rVert_p \le1\} denote the unit ℓp\ell_p ball. We formulate the problem of finding an approximate VI solution over the ℓp\ell_p ball as the following search problem.

Ballp_p-VI

  • Input: A 1-Lipschitz-continuous operator F:Bpd→RdF : B_p^d \to\mathbb{R}^d, represented by a well-behaved arithmetic circuit with rational constants and operations {+,−,×,min⁡,max⁡}\{+,-,\times,\min,\max\}, and an accuracy parameter ϵ∈(0,1)\epsilon\in(0,1). All inputs are encoded in binary.

  • Output: A point x∈Bpdx \in B_p^d satisfying

Gap⁡Bpd(x;F):=max⁡x′∈Bpd⟨x′−x,F(x)⟩≤ϵ.\operatorname{Gap}_{B_p^d}(x;F) := \max_{x' \in B_p^d} \langle x' - x, F(x) \rangle\le\epsilon.

We call such a point an ϵ\epsilon-approximate VI solution. The above definition adopts the standard notion of well-behaved arithmetic circuits by Fearnley, Goldberg, Hollender, and Savani [ [22]. In this paper, we investigate the complexity of Ballp_p-VI for affine and quadratic polynomial operators, specified explicitly by their rational coefficients and monomials. It is straightforward to establish that for every fixed exponent p≥1p \ge1, and also for p=∞p = \infty, Ballp_p-VI belongs to PPAD for arbitrary binary encoded ϵ\epsilon; for completeness we provide the proof of the membership in Appendix § 9.

To begin with, we examine the case where the operator is affine. Our first main result extends the existing hardness results for the ℓ1\ell_1 and ℓ∞\ell_\infty balls to every ℓp\ell_p ball with fixed p≠2p \ne2.

Theorem 1.1 (Abridged version of Theorem 4.1). For every fixed rational exponent p≥1p \ge1 with p≠2p \ne2, there exists a constant cp>0c_p > 0 such that Ballp_p-VI is PPAD-complete for ϵ=d−cp\epsilon= d^{-c_p}. The hardness result holds even for affine operators.

For p=∞p = \infty, the above result holds even at constant approximation accuracy [44] (Bernasconi, Castiglioni, Celli, and Farina 2026). Notably, our hardness construction does not extend to the Euclidean case p=2p = 2. This turns out to reflect something more fundamental than a limitation of the construction: we show that every affine VI over the Euclidean ball can be solved in polynomial time.

Theorem 1.2 (Abridged version of Theorem 5.1). For affine operators, Ball2_2-VI can be solved in time polynomial in the input encoding length and log⁡(1/ϵ)\log(1/\epsilon).

Importantly, this result does not require common structural assumptions that guarantee tractability. For example, when F(x)=Ax+bF(x) = Ax + b and AA is symmetric, polynomial-time solvability follows from classical algorithms for quadratic optimization over a Euclidean ball [46, 47]. Indeed, a global maximizer of the quadratic function 12xTAx+bTx\frac{1}{2}x^{\mathsf{T}}Ax+b^{\mathsf{T}}x over the ball satisfies the corresponding VI. Theorem 1.2 extends this tractability to arbitrary, possibly nonsymmetric matrices AA.

One notable application of Theorem 1.2 concerns performative prediction, where the deployment of a model changes the underlying data distribution [43, 28], for example through strategic responses [29]. Our algorithm yields a polynomial-time algorithm for finding (first-order) performatively stable points under quadratic loss functions and affine distribution shifts when the parameter vector lies in a Euclidean ball. This is in stark contrast to the case where the parameter vector is constrained to be on a box [2]. Theorem 1.2 has further new implications in quadratic games as well as computing stationary points under linear temporal-difference updates [11]. We elaborate on these implications and their assumptions later in § 1.3.

Having established the tractability of affine VIs over the Euclidean ball, a natural question arises: does this tractability extend beyond affine operators? Our next result shows that this tractability vanishes once the operator becomes quadratic, as computing an approximate VI solution becomes PPAD-complete.

Theorem 1.3 (Abridged version of Theorem 6.5). There exists a constant c>0c > 0 such that Ball2\mathrm{Ball}_2-VI is PPAD-complete for ϵ=d−c\epsilon= d^{-c}. The hardness result holds even for quadratic operators.

Our main results are summarized in Table 1.

DomainOperatorComplexityAdditive gap
Euclidean ballAffinePolynomial timeAny ϵ>0\epsilon> 0
Euclidean ballQuadraticPPAD-completeInverse polynomial
ℓp\ell_p ball (p≠2p \ne2)AffinePPAD-completeInverse polynomial
ℓ1\ell_1 ballAffinePPAD-complete†^\daggerInverse polynomial
ℓ∞\ell_\infty ballAffinePPAD-complete‡^\ddaggerConstant

Table 1. Complexity of VIs on unit balls. In the ℓp\ell_p row, p∈(1,∞)∖{2}p \in(1,\infty)\setminus\{2\} is a fixed parameter. Our results are highlighted in the shaded cells. †\dagger: Chen, Deng, and Teng [2009]. ‡\ddagger: Rubinstein [2018], Bernasconi, Castiglioni, Celli, and Farina [2026].

Remark 1.4 (Case 0<p<10 < p < 1). We restrict our attention to p≥1p \ge1, since for 0<p<10 < p < 1, ∥⋅∥p\|\cdot\|_p does not satisfy the properties of a norm. In particular, BpdB_p^d is a nonconvex set and VI solutions in (VI) need not exist, even for affine operators.

Technical overview

A common ingredient in typical PPAD-hardness reductions is the simulation of logical and arithmetic gates through piecewise-linear functions [15, 12, 44, 18]. The main technical challenge in our setting is to implement such gates using affine or quadratic operators together with the geometry of ℓp\ell_p balls. To this end, all our main hardness reductions start from PureCircuit [18] and approximate its threshold functions through weighted discretization,1 but implement the required weights in different ways. For ℓp\ell_p balls with p≠2p \ne2, we exploit the geometry of the constraints to simulate the threshold functions while keeping the operator affine. The Euclidean ball presents a contrasting picture, since it is possible to obtain a polynomial-time algorithm for affine VIs. Nevertheless, we show that quadratic operators provide sufficient expressiveness to simulate the same threshold functions and establish PPAD-hardness.

In what follows, we first explain why standard game reductions do not directly apply, and then develop these technical ideas in more detail.

Why standard game reductions do not directly apply. Many game-theoretic reductions enforce gate constraints through unilateral deviations [15, 12, 44]. Since the feasible set is a product of strategy spaces, each player can change their strategy while all other players’ strategies remain fixed. Gate gadgets exploit this independence: an incorrect gate output gives some player a sufficiently profitable deviation, forcing every approximate equilibrium to simulate the gate correctly (up to the required tolerance). However, this product structure is not essential for all equilibrium reductions. In particular, a symmetric equilibrium of a symmetric bimatrix game can be characterized by a single mixed strategy, whose best-response conditions can be expressed as an affine VI over the simplex [39].

This argument does not directly extend to a single ℓp\ell_p ball with 1<p<∞1 < p < \infty. On one hand, all coordinates share a common norm constraint, so changing one coordinate may in turn require further adjustments to others to preserve feasibility. As a result, the usual argument that hinges on independent deviations does not apply. Moreover, its curved boundary lacks the geometric properties needed for the symmetric encoding.

One possible alternative is to encode the desired gate or equilibrium conditions as polynomial equations and use their residuals as the VI operator. However, this approach introduces another challenge. If a VI solution lies in the interior, the operator must vanish, and hence all the intended equations are satisfied. At the boundary, however, the operator may be nonzero while still satisfying the VI optimality condition. A valid reduction must therefore ensure that every sufficiently accurate VI solution, including those on the boundary, can be decoded into an approximate solution of the original problem.

Non-Euclidean geometry. We first consider affine VIs over an ℓp\ell_p ball, where 1<p<∞1 < p < \infty and p≠2p \ne2. Although affine operators cannot directly implement the threshold functions of PureCircuit, the curvature of these non-Euclidean balls induces nonlinear behavior through the VI optimality condition. In particular, consider a coordinate xix_i whose operator component is Fi(x)=h(x)−xiF_i(\mathbf{x}) = h(\mathbf{x}) - x_i, where hh is an affine function. At a boundary solution x∗\mathbf{x}^*, the VI condition requires

h(x∗)−xi∗=λ∣xi∗∣p−2xi∗h(\mathbf{x}^*) - x_i^* = \lambda|x_i^*|^{p-2}x_i^*

for some λ≥0\lambda\ge0. Let σλ\sigma_\lambda denote the inverse of the function t↦t+λ∣t∣p−2tt \mapsto t + \lambda|t|^{p-2}t, which is nonlinear whenever p≠2p \ne2 and λ>0\lambda> 0. The boundary condition can therefore be written as

xi∗=σλ(h(x∗)).x_i^* = \sigma_\lambda(h(\mathbf{x}^*)).

In other words, the boundary VI condition naturally implements a nonlinear inverse mapping σλ\sigma_\lambda, even though the operator itself remains affine. At p=2p = 2, however, the inverse mapping reduces to σλ(t)=t/(1+λ)\sigma_\lambda(t) = t/(1 + \lambda), which is linear. This distinction explains precisely why our reduction does not extend to the Euclidean case.

To simulate the threshold functions of PureCircuit [18] (Bernasconi and Castiglioni 2026), we seek to exploit the nonlinearity of the inverse mapping σλ\sigma_\lambda. We first consider the finite difference

Δλ(t):=σλ(t+1)−2σλ(t)+σλ(t−1),\Delta_\lambda(t) := \sigma_\lambda(t + 1) - 2\sigma_\lambda(t) + \sigma_\lambda(t - 1),

which serves as a discrete analogue of the second derivative of σλ\sigma_\lambda. In the Euclidean case, σλ\sigma_\lambda is linear, so Δλ(t)=0\Delta_\lambda(t) = 0 for every tt. For p≠2p \ne2, however, Δλ\Delta_\lambda captures the curvature of σλ\sigma_\lambda and decays to zero at a polynomial rate in the tails. This tail decay suggests a way to approximate the threshold functions: we sample their values on a finite grid and combine them through weighted averaging. The polynomial decay would assign small weights to distant samples, limiting their contributions to the approximation. However, Δλ(t)\Delta_\lambda(t) can take both positive and negative values, whereas our construction requires nonnegative weights.

To overcome this obstruction, we construct a weight function through another finite difference of σλ\sigma_\lambda, namely

kλ(t):=ςp(σλ(4+Δλ(t)4)+σλ(4−Δλ(t)4)−2σλ(4)),k_\lambda(t) := \varsigma_p \left(\sigma_\lambda\left(4 + \frac{\Delta_\lambda(t)}{4}\right) + \sigma_\lambda\left(4 - \frac{\Delta_\lambda(t)}{4}\right) - 2\sigma_\lambda(4)\right),

where ςp=sgn⁡(2−p)\varsigma_p = \operatorname{sgn}(2 - p). Since σλ\sigma_\lambda is convex when 1<p<21 < p < 2 and concave when p>2p > 2 on the domain of interest, the sign factor ςp\varsigma_p ensures that kλk_\lambda is nonnegative for every tt. Moreover, when λ\lambda is sufficiently close to 1, this construction yields a polynomial tail bound kλ(t)=O(∣t∣−βp)k_\lambda(t) = O(|t|^{-\beta_p}) for some βp>2\beta_p > 2.

These properties allow us to control the error of the weighted approximation. By Lipschitz continuity, samples within distance 1/A1/A of the input have function values differing from the target by at most O(1/A)O(1/A). Meanwhile, the polynomial tail bound ensures that the total normalized contribution of other distant samples is at most O(A1−βp)O(A^{1-\beta_p}). Since βp>2\beta_p > 2, both errors become small as AA increases. Choosing a sufficiently fine grid then yields the desired approximation accuracy. Thus, by replacing the threshold functions with compactly supported versions, we can approximate the desired gates through weighted averaging using kλk_\lambda.

Two issues remain in implementing this construction. First, each coordinate can implement the nonlinear inverse mapping σλ\sigma_\lambda only through the boundary VI condition. Second, the threshold function approximation requires the common multiplier λ\lambda to be sufficiently close to one. We address both issues by introducing an anchor coordinate z0z_0 with a constant positive operator component F0=cRF_0 = c_R. This positive component prevents the operator from vanishing, forcing every exact VI solution to lie on the boundary. Moreover, by carefully choosing the radius RR and the constant cRc_R, we ensure that λ\lambda remains sufficiently close to one, where the weighted approximations achieve the desired accuracy. For approximate VI solutions, a sufficiently small VI gap ensures that the simulated PureCircuit gates satisfy their constraints within the required tolerance.

Finally, we rescale the construction to the unit ℓp\ell_p ball and normalize the operator coefficients, preserving PPAD-hardness at inverse-polynomial accuracy. The endpoint cases p=1p = 1 and p=∞p = \infty follow from hardness results for bimatrix Nash equilibria [12] and affine VIs over the hypercube [44] (Bernasconi, Castiglioni, Celli, and Farina 2026), respectively. Figure 1 illustrates how weighted averaging yields an approximation N~f\widetilde{N}_f of a threshold function.

References

  1. [1]Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, and Jingming Yan. The complexity of symmetric equilibria in min-max optimization and team zero-sum games. In Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2502.08519
  2. [2]Ioannis Anagnostides, Rohan Chauhan, Ioannis Panageas, Tuomas Sandholm, and Jingming Yan. On the computational complexity of performative prediction. In International Conference on Machine Learning (ICML), 2026a.arxiv.org/abs/2601.20180
  3. [3]Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, and Brian Hu Zhang. A polynomial-time algorithm for variational inequalities under the Minty condition. In Symposium on Foundations of Computer Science (FOCS), 2026b.arxiv.org/abs/2504.03432
  4. [4]Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm, and Jingming Yan. The computational complexity of team zero-sum games. In Symposium on Discrete Algorithms (SODA), 2027.arxiv.org/abs/2606.16139
  5. [5]Idan Attias, Yuval Dagan, Constantinos Daskalakis, Rui Yao, and Manolis Zampetakis. Fixed point computation: Beating brute force with smoothed analysis. arXiv preprint arXiv:2501.10884, 2025.
  6. [6]Keith Ball, Eric A. Carlen, and Elliott H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones Mathematicae, 115(3):463–482, 1994.
  7. [7]Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Monotone contractions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 507–517, 2025.arxiv.org/abs/2411.10107
  8. [9]Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina. Improved hardness results for min-max optimization with coupled constraints. In Conference on Economics and Computation (EC), 2026.
  9. [10]Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Alexandros Hollender. The complexity of min–max optimization for quadratic polynomials. In Symposium on Discrete Algorithms (SODA), 2027.
  10. [11]Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. Operations Research, 69(3):950–973, 2021. doi: 10.1287/opre.2020.2024.
  11. [12]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):14:1–14:57, 2009. doi: 10.1145/1516512.1516516.
  12. [13]Xi Chen, Dimitris Paparas, and Mihalis Yannakakis. The complexity of non-monotone markets. Journal of the ACM, 64(3):20:1–20:56, 2017. doi: 10.1145/3064810.DOI
  13. [14]Xi Chen, Yuhao Li, and Mihalis Yannakakis. Computing a fixed point of contraction maps in polynomial queries. Journal of the ACM, 72(4):1–20, 2025.
  14. [15]Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009.
  15. [16]Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Symposium on Theory of Computing (STOC), 2021.
  16. [17]Constantinos Daskalakis, Gabriele Farina, and Brian Hu Zhang. Polynomial-time computation of ℓₚ-contraction fixed points for even p. In Symposium on Discrete Algorithms (SODA), 2027.
  17. [18]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure-Circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):31:1–31:48, 2024.DOI
  18. [19]Kousha Ettessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531–2597, 2010. doi: 10.1137/080720826.
  19. [20]Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, 2003.
  20. [21]John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. Journal of Computer and System Sciences, 114:1–35, 2020.arxiv.org/abs/1811.03841
  21. [22]John Fearnley, Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. Journal of the ACM, 70(1):7:1–7:74, 2023.
  22. [23]John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of computing KKT solutions of quadratic programs. Journal of the ACM, 72(5):31:1–31:48, 2025. doi: 10.1145/3745017.DOI
  23. [24]Abheek Ghosh and Alexandros Hollender. The complexity of symmetric bimatrix games with common payoffs. In International Workshop On Internet And Network Economics (WINE), 2024.
  24. [25]Paul W Goldberg and Alexandros Hollender. The hairy ball problem is ppad-complete. Journal of Computer and System Sciences, 122:34–62, 2021.DOI
  25. [26]Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
  26. [27]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 2nd edition, 1993.
  27. [28]Moritz Hardt and Celestine Mendler-Dünner. Performative prediction: Past and future. Statistical Science, 40(3):417–436, 2025.
  28. [29]Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Innovations in Theoretical Computer Science (ITCS), 2016.
  29. [30]Philip Hartman and Guido Stampacchia. On some non-linear elliptic differential-functional equations. Acta Mathematica, 115:271–310, 1966. doi: 10.1007/BF02392210.DOI
  30. [31]Sebastian Haslebacher, Jonas Lill, Patrick Schnider, and Simon Weber. Query-efficient fixpoints of ℓₚ-contractions. TheoretiCS, 5, 2026.
  31. [32]Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580, 2012.arxiv.org/abs/1207.0580
  32. [33]Jian Hou, Zong-Chuan Wen, and Zhu Wen. A variational inequality method for computing a normalized equilibrium in the generalized Nash game. Journal of Inequalities and Applications, 2012:60, 2012. doi: 10.1186/1029-242X-2012-60.DOI
  33. [34]Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976.
  34. [35]Mikhail K. Kozlov, Sergei P. Tarasov, and Leonid G. Khachiyan. The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics, 20(5):223–228, 1980. doi: 10.1016/0041-5553(80)90098-1.DOI
  35. [36]Arkadi Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004. doi: 10.1137/S1052623403425629.DOI
  36. [37]Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319–344, 2007.DOI
  37. [38]Jiawang Nie, Defeng Sun, Xindong Tang, and Min Zhang. Solving polynomial variational inequality problems via Lagrange multiplier expressions and Moment-SOS relaxations. Computational Optimization and Applications, 90:361–394, 2025. doi: 10.1007/s10589-024-00635-y.DOI
  38. [39]Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, USA, 2007.
  39. [40]Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.DOI
  40. [41]Pablo A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96:293–320, 2003. doi: 10.1007/s10107-003-0387-5.DOI
  41. [42]Pablo A. Parrilo. Polynomial games and sum of squares optimization. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 2855–2860, 2006. doi: 10.1109/CDC.2006.377261.DOI
  42. [43]Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning (ICML), 2020.arxiv.org/abs/2002.06673
  43. [44]Aviad Rubinstein. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3):917–959, 2018. doi: 10.1137/15M1039274.DOI
  44. [45]Noah D. Stein, Pablo A. Parrilo, and Asuman Ozdaglar. Correlated equilibria in continuous games: Characterization and computation. Games and Economic Behavior, 71(2):436–455, 2011. doi: 10.1016/j.geb.2010.04.004.DOI
  45. [46]Stephen A. Vavasis and Richard Zippel. Proving polynomial-time for sphere-constrained quadratic programming. Technical Report 90-1182, Department of Computer Science, Cornell University, 1990. URL https://hdl.handle.net/1813/7022.
  46. [47]Yinyu Ye. A new complexity result on minimization of a quadratic function with a sphere constraint. In Christodoulos A. Floudas and Panos M. Pardalos, editors, Recent Advances in Global Optimization, pages 19–31. Princeton University Press, 1992. doi: 10.1515/9781400862528.19.

Paper details

vlnc:W_f6huceqn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6, GPT-6.0

View statement
Looking for related papers…
Contents