Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BROUWER'S FIXED POINT:
Reports tagged with Brouwer's fixed point:
TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

#### Computing Nash Equilibria: Approximation and Smoothed Complexity

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an \$n\times ... more >>>

TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

#### On the Complexity of 2D Discrete Fixed Point Problem

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

ISSN 1433-8092 | Imprint