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