All reports by Author Xiaotie Deng:

__
TR17-118
| 20th July 2017
__

Xiaotie Deng, Zhe Feng, Rucha Kulkarni#### Octahedral Tucker is PPA-Complete

Revisions: 1

__
TR15-120
| 12th July 2015
__

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi#### Understanding PPA-Completeness

Revisions: 1

__
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

__
TR05-074
| 8th June 2005
__

Li-Sha Huang, Xiaotie Deng#### On Complexity of Market Equilibria with Maximum Social Welfare

Xiaotie Deng, Zhe Feng, Rucha Kulkarni

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

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

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

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 >>>Li-Sha Huang, Xiaotie Deng

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