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

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

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)

Cites Work

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

Cited In (21)

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

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)