On the complexity of 2D discrete fixed point problem

DOI10.1016/J.TCS.2009.07.052zbMATH Open1183.68294OpenAlexW1826384874MaRDI QIDQ1035680FDOQ1035680

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

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

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

(22)

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

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)