清华大学交叉信息研究院

陈汐
Email:
地址: 清华大学FIT楼4区609房间


Education Background:


  I am now a fourth-year PhD student in the department of Computer Science at Tsinghua University. I studied in the department of PhysITCS 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.

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.