Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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


We show that:

1. Computing n copies of a function requires sqrt{n} times the ... 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 >>>

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

TR05-140 | 30th November 2005
Xi Chen, Xiaotie Deng

Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

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

more >>>

TR05-134 | 17th November 2005
Xi Chen, Xiaotie Deng

3-NASH is PPAD-Complete

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

ISSN 1433-8092 | Imprint