Publications

 

Book:

Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain
Jin-Yi Cai and Xi Chen, Cambridge University Press, 2017

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:

Learning and Testing Junta Distributions with Subcube Conditioning [ARXIV]
Xi Chen, Rajesh Jayaram, Amit Levi and Erik Waingarten

Random Restrictions of High-Dimensional Distributions and Uniformity Testing
with Subcube Conditioning [ECCC]
Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi and Erik Waingarten

A Lower Bound on Cycle-Finding in Sparse Digraphs [SODA 20]
Xi Chen, Tim Randolph, Rocco Servedio and Timothy Sun

Nearly Optimal Edge Estimation with Independent Set Queries [SODA 20]
Xi Chen, Amit Levi and Erik Waingarten

Testing Unateness Nearly Optimally [STOC 19]
Xi Chen and Erik Waingarten

Distribution-free Junta Testing [STOC 18]
Xi Chen, Zhengyang Liu, Rocco Servedio, Ying Sheng and Jinyu Xie

Adaptivity is Exponentially Powerful for Testing Monotonicity of Halfspaces
[RANDOM 17]
Xi Chen, Rocco Servedio, Li-Yang Tan and Erik Waingarten

Sample-based High-dimensional Convexity Testing [RANDOM 17]
Xi Chen, Adam Freilich, Rocco Servedio and Timothy Sun

Boolean Unateness Testing with O(n^{3/4}) Adaptive Queries [FOCS 17]
Xi Chen, Erik Waingarten and Jinyu Xie

Settling the Query Complexity of Non-adaptive Junta Testing [CCC 17, Best paper award]
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten and Jinyu Xie

Beyond Talagrand Functions: New Lower Bounds for Testing
Monotonicity and Unateness [STOC 17]
Xi Chen, Erik Waingarten and Jinyu Xie

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions [SODA 16]
Xi Chen and Jinyu Xie

Boolean Function Monotonicity Testing Requires (Almost) n^{1/2}
Non-adaptive Queries [STOC 15]
Xi Chen, Anindya De, Rocco A. Servedio and Li-Yang Tan

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

Algorithmic Game Theory and Economics:

Hedging in Games: Faster Convergence of External and Swap Regrets [ARXIV]
Xi Chen and Binghui Peng

An Axiomatic Approach to Block Rewards [AFT 19]
Xi Chen, Christos Papadimitriou and Tim Roughgarden

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer [SODA 18]
Xi Chen, George Matikas, Dimitris Paparas and Mihalis Yannakakis

Well-Supported versus Approximate Nash Equilibria: Query Complexity
of Large Games [ITCS 17]
Xi Chen, Yu Cheng and Bo Tang

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms [FOCS 15]
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun
and Mihalis Yannakakis.

On the Complexity of Nash Equilibria in Anonymous Games [STOC 15]
Xi Chen, David Durfee and Anthi Orfanou

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:

Smoothed Complexity of Local Max-Cut and Binary Max-CSP [STOC 20]
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis,
Mihalis Yannakakis and Xinzhi Zhang

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel [FOCS 19]
Frank Ban, Xi Chen, Adam Freilich, Rocco Servedio and Sandip Sinha

Efficient Average-case Population Recovery in the Presence of Insertions and Deletions [RANDOM 19]
Frank Ban, Xi Chen, Rocco Servedio and Sandip Sinha

Addition is Exponentially Harder than Counting for Shallow
Monotone Circuits [STOC 17]
Xi Chen, Igor C. Oliveira and Rocco A. Servedio

On the Recursive Teaching Dimension of VC Classes [NIPS 16]
Xi Chen, Yu Cheng and Bo Tang

Near-optimal Small-depth Lower Bounds for Small Distance Connectivity [STOC 16]
Xi Chen, Igor C. Oliveira, Rocco A. Servedio and Li-Yang Tan

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