Publications

 

Surveys:

Recent Development in Computational Complexity Characterization of
Nash equilibrium, Computer Science Review 1(2): 88-99, 2007
Xi Chen and Xiaotie Deng

Partial Derivatives in Arithmetic Complexity and Beyond, Foundations
and Trends in Theoretical Computer Science 6(1-2), 2010
Xi Chen, Neeraj Kayal and Avi Wigderson

Complexity Dichotomies of Counting Problems, SIGACT News
Complexity Theory Column 72, 42(4), December 2011
Xi Chen


Property Testing:

New Algorithms and Lower Bounds for Monotonicity Testing [FOCS 14]
Xi Chen, Rocco Servedio and Li-Yang Tan

Complexity of Equilibria:

The Complexity of Optimal Multidimensional Pricing [SODA 14]
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun and Mihalis Yannakakis

The Complexity of Non-Monotone Markets [STOC 13]
Xi Chen, Dimitris Paparas and Mihalis Yannakakis

A Complexity View of Markets with Social Influence  [ICS 11]
Xi Chen and Shang-Hua Teng,

Spending is not Easier than Trading: On the Computational Equivalence of
Fisher and Arrow-Debreu Equilibria  [
ISAAC 09, Best paper award]
Xi Chen and Shang-Hua Teng

Settling the Complexity of Arrow-Debreu Equilibria in Markets with
Additively Separable Utilities  [
FOCS 09]
Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng

Setlling the Complexity of Computing Two-Player Nash Equilibria
Journal of the ACM 56 (3), 2009  [Journal version of the two FOCS 06 papers]
Xi Chen, Xiaotie Deng and Shang-Hua Teng

The Approximation Complexity of Win-Lose Games  [SODA 07]
Xi Chen, Shang-Hua Teng and Paul Valiant

Sparse Games are Hard  [WINE 06]
Xi Chen, Xiaotie Deng and Shang-Hua Teng

Market Equilibria with Hybrid Linear-Leontief Utilities
Theoretical Computer Science 410: 1573–1580, 2009  [WINE 06]
Xi Chen, Li-Sha Huang and Shang-Hua Teng

Computing Nash Equilibria: Approximation and Smoothed Complexity  [FOCS 06
Xi Chen, Xiaotie Deng and Shang-hua Teng

3-NASH is PPAD-Complete  [ECCC Report]
Xi Chen and Xiaotie Deng

Settling the Complexity of 2-Player Nash Equilibrium  [FOCS 06, Best paper award]
Xi Chen and Xiaotie Deng


Graph Isomorphism Testing:

Faster Canonical Forms for Strongly Regular Graphs [FOCS 13]
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng and John Wilmes

Stage Design for Quasipolynomial-Time Isomorphism Testing for
Steiner 2-Systems [STOC 13]
Xi Chen, Xiaorui Sun and Shang-Hua Teng


Complexity Theory:

The Complexity of Approximating Conservative Counting CSPs [STACS 13]
Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu,
Colin McQuillan and David Richerby

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems [COCOA 12]
Jin-Yi Cai, Xi Chen, Heng Guo and Pinyan Lu

Complexity of Counting CSP with Complex Weights [STOC 12]
Jin-Yi Cai and Xi Chen

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy [CCC 11]
Jin-Yi Cai, Xi Chen and Pinyan Lu

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with
Non-negative Weights  [
FOCS 10]
Jin-Yi Cai and Xi Chen

On Tractable Exponential Sums  [FAW 10, Best paper award]
Jin-Yi Cai, Xi Chen, Richard Lipton and Pinyan Lu

How to Compress Interactive Communication  [STOC 10]
to appear in SIAM Journal on Computing
Boaz Barak, Mark Braverman, Xi Chen and Anup Rao

Graph Homomorphisms with Complex Values: A Dichotomy Theorem  [ICALP 10]
to appear in SIAM Journal on Computing
Jin-Yi Cai, Xi Chen and Pinyan Lu

Quadratic Lower Bound for the Permanent and Determinant Problem over any Characteristic \ne 2, Computational Complexity 19: 37–56, 2010  [STOC 08]
Jin-Yi Cai, Xi Chen and Dong Li


Fixed-Point Computation:

Matching Algorithmic Bounds for Finding a Brouwer Fixed Point
Journal of the ACM 55 (3), 2008  [STOC 05]
Xi Chen and Xiaotie Deng

Quantum Separation of Local Search and Fixed Point Computation
Algorithmica 56: 364–382, 2010  [COCOON 08]
Xi Chen, Xiaoming Sun and Shang-Hua Teng

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

A Simplicial Approach for Discrete Fixed Point Theorems
Algorithmica 53: 250–262, 2009  [COCOON 06]
Xi Chen and Xiaotie Deng

On the Complexity of 2D Discrete Fixed Point Problem
Theoretical Computer Science 410 (44), 2009  [ICALP 06
Xi Chen and Xiaotie Deng

Lattice Embedding of Direction-Preserving Correspondence Over Integrally
Convex Set  [AAIM 06] 
Xi Chen and Xiaotie Deng


Others:

Computing Exact p-Value for Structured Motif  [CPM 07]
Jing Zhang, Xi Chen and Ming Li

On Searching a Table Consistent with Division Poset
Theoretical Computer Science 370: 240–253, 2007
Yongxi Cheng, Xi Chen and Yiqun L. Yin

On Incentive Compatible Competitive Selection Protocol 
to appear in Algorithmica  [COCOON 06]
Xi Chen, Xiaotie Deng and Becky Jie Liu

Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem
Theoretical Computer Science 378: 316–330, 2007  [ISAAC 05]
Lan Liu, Xi Chen, Jing Xiao and Tao Jiang