Unique end of potential line

DOI10.1016/j.jcss.2020.05.007zbMath1461.68086arXiv1811.03841OpenAlexW2966513741MaRDI QIDQ2194856

Rahul Savani, John Fearnley, Spencer Gordon, Ruta Mehta

Publication date: 7 September 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.03841

zbMATH Keywords

contraction mapP-matrix linear complementarity problemTFNPunique sink orientationcontinuous local searchtotal search problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unnamed Item ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Unnamed Item ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unnamed Item ⋮ The complexity of the parity argument with potential ⋮ Adventures in monotone complexity and TFNP ⋮ Unique End of Potential Line ⋮ The complexity of finding fair independent sets in cycles ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Uses Software

• BEDFix

Cites Work

• Unnamed Item
• 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
• Optimal solution of nonlinear equations
• NP-completeness of the linear complementarity problem
• Completely unimodal numberings of a simple polytope
• How easy is local search?
• An interior point potential reduction algorithm for the linear complementarity problem
• A unified approach to interior point algorithms for linear complementary problems
• On the complexity of the parity argument and other inefficient proofs of existence
• The P-matrix problem is co-NP-complete
• The complexity of mean payoff games on graphs
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• A recursive algorithm for the infinity-norm fixed point problem
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Approximating fixed points of weakly contracting mappings
• Computational complexity of fixed points
• A note on two fixed point problems
• 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
• Simple Local Search Problems that are Hard to Solve
• 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
• Jumping Doesn’t Help in Abstract Cubes
• Computational complexity of complementary pivot methods
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• The Random‐Facet simplex algorithm on combinatorial cubes
• THREE PUZZLES ON MATHEMATICS, COMPUTATION, AND GAMES
• The Complexity of All-switches Strategy Improvement
• The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
• 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
• Unique End of Potential Line
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
• 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