Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xiaotie Deng:

TR17-118 | 20th July 2017
Xiaotie Deng, Zhe Feng, Rucha Kulkarni

Octahedral Tucker is PPA-Complete

Revisions: 1

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

TR15-120 | 12th July 2015
Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

Understanding PPA-Completeness

Revisions: 1

The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of 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 >>>

TR05-074 | 8th June 2005
Li-Sha Huang, Xiaotie Deng

On Complexity of Market Equilibria with Maximum Social Welfare

We consider the computational complexity of the market equilibrium
problem by exploring the structural properties of the Leontief
exchange economy. We prove that, for economies guaranteed to have
a market equilibrium, finding one with maximum social welfare or
maximum individual welfare is NP-hard. In addition, we prove that
counting the ... more >>>

ISSN 1433-8092 | Imprint