	Name: Xi Chen
	Address: Institute for Theoretical Computer Science, Tsinghua University, Beijing, 100084, P. R. China
	Office: Room 4-609 FIT Building
	Telephone: 86-10-62797304
	Email: csxincheng@gmails.com
	Join Time: 2003

Education Background	Research Interests	Awards
Publications	Telephone and Email

I am now a fourth-year PhD student in the department of Computer Science at Tsinghua University. I studied in the department of Physics of Tsinghua University and received my B.S. there in 2003. My advisor is Prof. Zhang, and I am a member of the theory group led by Prof. Yao.

Research Interests:

My research interests lie in the area of Theoretical Computer Science. I am particularly interested in the computational complexity of natural problems in Algorithmic Game Theory and Computational Biology.

Awards:

Xi Chen and Xiaotie Deng, Settling the Complexity of 2-Player Nash-Equilibrium, FOCS 06, Best Paper Award.

Publications:

1	Xi Chen and Shang-Hua Teng, Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation, FOCS 07.

2	Xi Chen, Shang-Hua Teng and Paul Valiant, The Approximation Complexity of Win-Lose Games, SODA 07.
3	Xi Chen, Xiaotie Deng and Shang-Hua Teng, Sparse Games are Hard, WINE 06.
4	Xi Chen, Li-Sha Huang and Shang-Hua Teng, Market Equilibria with Hybrid Linear-Leontief Utilities, WINE 06.
5	Xi Chen and Xiaotie Deng, A Simplicial Approach for Discrete Fixed Point Theorems, COCOON 06.
6	Xi Chen, Xiaotie Deng and Becky Jie Liu, On Incentive Compatible Competitive Selection Protocol, COCOON 06.
7	Xi Chen and Xiaotie Deng, On the Complexity of 2D Discrete Fixed Point Problem, ICALP 06.
8	Xi Chen and Xiaotie Deng, Lattice Embedding of Direction-Preserving Correspondence Over Integrally Convex Set, AAIM 06.
9	Xi Chen, Xiaotie Deng and Shang-hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, FOCS 06.
10	Xi Chen and Xiaotie Deng, Settling the Complexity of 2-Player Nash-Equilibrium, FOCS 06.
11	Lan Liu, Xi Chen, Jing Xiao and Tao Jiang, Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem, ISAAC 05.
12	Xi Chen and Xiaotie Deng, On Algorithms for Discrete and Approximate Brouwer Fixed Points, STOC 05.

Telephone and Email:

	Telephone: 86-10-62797304
	Email: csxincheng@gmails.com

Back