Publications:
Xi Chen, Xiaoming Sun and Shang-Hua Teng, Quantum Sepration of
Local Search and Fixed Point Computation, to appear in COCOON 2008.
Jin-Yi Cai, Xi Chen and Dong Li, A quadratic lower bound for the
permanent and determinant problem over any characteristic \ne 2,
to appear in STOC 2008 [manuscript].
Jing Zhang, Xi Chen and Ming Li, Computing exact p-value for
structured motif. [CPM 2007]
Xi Chen and Shang-Hua Teng, Paths Beyond Local Search: A Tight
Bound for Randomized Fixed-Point Computation, [FOCS 07][Arxiv]
Yongxi Cheng, Xi Chen and Yiqun L. Yin, On Searching a Table Consistent
with Division Poset, Theoretical Computer Science 370, 240–253, 2007.
Xi Chen, Shang-Hua Teng and Paul Valiant, The Approximation
Complexity of Win-Lose Games. [SODA 07]
Xi Chen, Xiaotie Deng and Shang-Hua Teng, Sparse Games are
Hard. [WINE 06]
Xi Chen, Li-Sha Huang and Shang-Hua Teng, Market Equilibria
with Hybrid Linear-Leontief Utilities. [WINE 06]
Xi Chen and Xiaotie Deng, A Simplicial Approach for Discrete
Fixed Point Theorems. [COCOON 06]
Xi Chen, Xiaotie Deng and Becky Jie Liu, On Incentive Compatible
Competitive Selection Protocol. [COCOON 06]
Xi Chen and Xiaotie Deng, On the Complexity of 2D Discrete Fixed
Point Problem. [ICALP 06] [ECCC Report]
Xi Chen and Xiaotie Deng, Lattice Embedding of Direction-Preserving
Correspondence Over Integrally Convex Set. [AAIM 06]
Xi Chen, Xiaotie Deng and Shang-hua Teng, Computing Nash Equilibria:
Approximation and Smoothed Complexity. [FOCS 06, ECCC Report]
Xi Chen and Xiaotie Deng, 3-NASH is PPAD-Complete. [ECCC Report]
Xi Chen and Xiaotie Deng, Settling the Complexity of 2-Player
Nash-Equilibrium. [FOCS 06, ECCC Report]
Lan Liu, Xi Chen, Jing Xiao and Tao Jiang, Complexity and Approximation of
the Minimum Recombination Haplotype Configuration Problem. [ISAAC 2005]
Xi Chen and Xiaotie Deng, On Algorithms for Discrete and Approximate
Brouwer Fixed Points. [STOC 2005][Full]