All reports by Author Xi Chen:

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR06-037
| 10th February 2006
__

Xi Chen, Xiaotie Deng#### On the Complexity of 2D Discrete Fixed Point Problem

__
TR06-023
| 7th February 2006
__

Xi Chen, Xiaotie Deng, Shang-Hua Teng#### Computing Nash Equilibria: Approximation and Smoothed Complexity

__
TR05-140
| 30th November 2005
__

Xi Chen, Xiaotie Deng#### Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

__
TR05-134
| 17th November 2005
__

Xi Chen, Xiaotie Deng#### 3-NASH is PPAD-Complete

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

Xi Chen, Xiaotie Deng

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 >>>

Xi Chen, Xiaotie Deng, Shang-Hua Teng

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 >>>

Xi Chen, Xiaotie Deng

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

more >>>Xi Chen, Xiaotie Deng

In this paper, we improve a recent result of Daskalakis, Goldberg and Papadimitriou on PPAD-completeness of 4-Nash, showing that 3-Nash is PPAD-complete.

more >>>