Unique End of Potential Line
From MaRDI portal
Publication:5091211
DOI10.4230/LIPIcs.ICALP.2019.56OpenAlexW2969529327MaRDI QIDQ5091211
Rahul Savani, John Fearnley, Spencer Gordon, Ruta Mehta
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10632/pdf/LIPIcs-ICALP-2019-56.pdf
contraction mapP-matrix linear complementarity problemTFNPunique sink orientationcontinuous local searchtotal search problems
Related Items (4)
Unique end of potential line ⋮ PPAD is as hard as LWE and iterated squaring ⋮ The stochastic arrival problem ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On total functions, existence theorems and computational complexity
- Integer factoring and modular square roots
- Exponential lower bounds for finding Brouwer fixed points
- On the complexity of 2D discrete fixed point problem
- Minimization algorithms and random walk on the d-cube
- Completely unimodal numberings of a simple polytope
- How easy is local search?
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- The complexity of stochastic games
- An interior point potential reduction algorithm for the linear complementarity problem
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Approximating fixed points of weakly contracting mappings
- Unique end of potential line
- A note on two fixed point problems
- Random edge can be exponential on abstract cubes
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Discrete Fixed Points: Models, Complexities, and Applications
- The Complexity of Recognizing Unique Sink Orientations
- On the Complexity of Nash Equilibria and Other Fixed Points
- Computing Stable Outcomes in Hedonic Games
- The Linear Complementarity Problem
- Settling the complexity of computing two-player Nash equilibria
- Matching algorithmic bounds for finding a Brouwer fixed point
- The complexity of pure Nash equilibria
- On algorithms for discrete and approximate brouwer fixed points
- Linear programming and unique sink orientations
- Computational complexity of complementary pivot methods
- The Random‐Facet simplex algorithm on combinatorial cubes
- THREE PUZZLES ON MATHEMATICS, COMPUTATION, AND GAMES
- The Complexity of All-switches Strategy Improvement
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP
- ARRIVAL: Next Stop in CLS
- The Complexity of Computing a Nash Equilibrium
- A converse to Banach's fixed point theorem and its CLS-completeness
- Constant rank bimatrix games are PPAD-hard
- The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games
- Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
- Bimatrix Equilibrium Points and Mathematical Programming
This page was built for publication: Unique End of Potential Line
