On the Complexity of 2D Discrete Fixed Point Problem

DOI10.1007/11786986_43zbMATH Open1223.68054OpenAlexW2584543285MaRDI QIDQ3613784FDOQ3613784

Authors: Xi Chen, Xiaotie Deng 

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_43

Recommendations

• On the complexity of 2D discrete fixed point problem
• On the complexity of a two-point boundary value problem in different settings
• Computational complexity of fixed points and intersection points
• Computational complexity of fixed points
• Complexity of fixed point computation
• Complexity of nonlinear two-point boundary-value problems
• The scheme complexity of discrete optimization
• A simplicial approach for discrete fixed point theorems
• A Simplicial Approach for Discrete Fixed Point Theorems
• On the functional complexity of a two-dimensional interval search problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (11)

• Quantum and classical query complexities of local search are polynomially related
• On the black-box complexity of Sperner's Lemma
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• Constant rank two-player games are PPAD-hard
• A simplicial approach for discrete fixed point theorems
• 2-D Tucker is PPA complete
• Recent development in computational complexity characterization of Nash equilibrium
• On the complexity of 2D discrete fixed point problem
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Colorful linear programming, Nash equilibrium, and pivots
• \(\mathsf{PPAD}\)-completeness of polyhedral versions 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 Q3613784)