On the Complexity of 2D Discrete Fixed Point Problem

DOI10.1007/11786986_43MaRDI QIDQ3613784zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(11)

• On the black-box complexity of Sperner's Lemma
• Quantum and classical query complexities of local search are polynomially related
• A direct reduction from \(k\)-player to 2-player approximate Nash equilibrium
• A simplicial approach for discrete fixed point theorems
• Constant rank two-player games are PPAD-hard
• 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)