Fetching the paper…
Reading the bibliography…
The complexity class CLS was introduced by Daskalakis and Papadimitriou with the goal of capturing the complexity of some well-known problems in PPAD$~\cap~$PLS that have resisted, in some cases for decades, attempts to put them in polynomial time.
Bimatrix equilibrium points and mathematical programming
Carlton E Lemke · 1965
Earlier work this paper cites.
Orientation in complementary pivot algorithms
Michael J Todd · 1976
Earlier work this paper cites.
Computational complexity of complementary pivot methods
Katta G Murty · 1978
Earlier work this paper cites.
How easy is local search?
David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis · 1988
Earlier work this paper cites.
A note on the complexity of P-matrix LCP and computing an equilibrium
Nimrod Megiddo · 1988
Earlier work this paper cites.
NP-completeness of the linear complementarity problem
Sung-Jin Chung · 1989
Earlier work this paper cites.
On total functions, existence theorems and computational complexity
Nimrod Megiddo and Christos H Papadimitriou · 1991
Earlier work this paper cites.
Simple local search problems that are hard to solve
Alejandro A Schäffer and Mihalis Yannakakis · 1991
Earlier work this paper cites.
The complexity of stochastic games
Anne Condon · 1992
Earlier work this paper cites.
An interior point potential reduction algorithm for the linear complementarity problem
Masakazu Kojima, Nimrod Megiddo, and Yinyu Ye · 1992
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H Papadimitriou · 1994
Earlier work this paper cites.
A subexponential randomized algorithm for the simple stochastic game problem
Walter Ludwig · 1995
Cited alongside, same era.
Theory of hybrid systems and discrete event systems
Anuj Puri · 1996
Cited alongside, same era.
The complexity of mean payoff games on graphs
Uri Zwick and Mike Paterson · 1996
Cited alongside, same era.
Deciding the winner in parity games is in UP ∩ \cap
Marcin Jurdziński · 1998
Cited alongside, same era.
A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
Henrik Björklund, Sven Sandberg, and Sergei Vorobyov · 2004
Cited alongside, same era.
The complexity of pure Nash equilibria
Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar · 2004
The complexity of computing a Nash equilibrium
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou · 2009
Later among the works it cites.
Linear complementarity algorithms for infinite games
John Fearnley, Marcin Jurdziński, and Rahul Savani · 2010
Later among the works it cites.
Continuous local search
Constantinos Daskalakis and Christos Papadimitriou · 2011
Later among the works it cites.
The complexity of interior point methods for solving discounted turn-based stochastic games
Thomas Dueholm Hansen and Rasmus Ibsen-Jensen · 2013
Later among the works it cites.
On the cryptographic hardness of finding a Nash equilibrium
Nir Bitansky, Omer Paneth, and Alon Rosen · 2015
Later among the works it cites.
A complementary pivot algorithm for market equilibrium under separable piecewise-linear concave utilities
Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Simple stochastic games and P-matrix generalized linear complementarity problems
Bernd Gärtner and Leo Rüst · 2005
Cited alongside, same era.
A simple P-matrix linear complementarity problem for discounted games
Marcin Jurdziński and Rahul Savani · 2008
Cited alongside, same era.
Settling the complexity of computing two-player Nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Cited alongside, same era.
The linear complementarity problem
Richard W Cottle, Jong-Shi Pang, and Richard E Stone · 2009
Cited alongside, same era.
Deciding parity games in quasipolynomial time
Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan
Cited in the paper.
A Converse to Banach’s Fixed Point Theorem and its CLS Completeness
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis
Cited in the paper.
Later among the works it cites.
The complexity of all-switches strategy improvement
John Fearnley and Rahul Savani · 2016
Later among the works it cites.
Revisiting the cryptographic hardness of finding a Nash equilibrium
Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan · 2016
Later among the works it cites.
Hardness of continuous local search: Query complexity and cryptographic lower bounds
Pavel Hubáček and Eylon Yogev · 2017
Closest in time.
The rainbow at the end of the line: A PPAD formulation of the colorful Carathéodory theorem with applications
Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, and Yannik Stein · 2017
Closest in time.