On the complexity of 2D discrete fixed point problem

DOI10.1016/J.TCS.2009.07.052MaRDI QIDQ1035680zbMATH OpenOpenAlexFDO

Authors Xi Chen, Xiaotie Deng

Publication date 4 November 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.07.052

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the Complexity of 2D Discrete Fixed Point Problem
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Discrete fixed points: models, complexities, and applications
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Understanding PPA-completeness

Cites work

• A Sperner lemma complete for PPA
• Exponential lower bounds for finding Brouwer fixed points
• Fundamentals of Computation Theory
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• On algorithms for discrete and approximate brouwer fixed points
• On the complexity of the parity argument and other inefficient proofs of existence
• The complexity of computing a Nash equilibrium

Cited in

(30)

• On the complexity of the parity argument and other inefficient proofs of existence
• Computational complexity of fixed points and intersection points
• 2-D Tucker is PPA complete
• On the complexity of finding a Caristi's fixed point
• The complexity of finding fair independent sets in cycles
• Discrete versions of the KKM lemma and their PPAD-completeness
• Unique end of potential line
• Understanding PPA-completeness
• The Hairy Ball problem is PPAD-complete
• Envy-free cake division without assuming the players prefer nonempty pieces
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Matching algorithmic bounds for finding a Brouwer fixed point
• On the Complexity of 2D Discrete Fixed Point Problem
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Unique End of Potential Line
• The Hairy Ball Problem is PPAD-Complete.
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Fundamentals of Computation Theory
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The complexity of gradient descent: CLS = PPAD pls
• Computations and complexities of Tarski's fixed points and supermodular games
• Tree polymatrix games are PPAD-hard
• Envy-free cake-cutting for four agents
• Computing a fixed point of contraction maps in polynomial queries
• Computations and complexities of Tarski's fixed points and supermodular games
• Pure-circuit: tight inapproximability for PPAD
• The complexity of finding fair independent sets in cycles
• Settling the complexity of Nash equilibrium in congestion games
• On the black-box complexity of Sperner's Lemma

This page was built for publication: On the complexity of 2D discrete fixed point problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1035680)