Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem. - Lan Liu 001; Xi Chen 001; Jing Xiao; Tao Jiang 001 (ISAAC, 2005)

On algorithms for discrete and approximate brouwer fixed points. - Xi Chen 001; Xiaotie Deng (STOC, 2005)

3-NASH is PPAD-Complete - Xi Chen 001; Xiaotie Deng (Electron. Colloquium Comput. Complex., 2005)

Settling the Complexity of 2-Player Nash-Equilibrium - Xi Chen 001; Xiaotie Deng (Electron. Colloquium Comput. Complex., 2005)

Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set. - Xi Chen 001; Xiaotie Deng (AAIM, 2006)

On Incentive Compatible Competitive Selection Protocol. - Xi Chen 001; Xiaotie Deng; Becky Jie Liu (COCOON, 2006)

Settling the Complexity of Two-Player Nash Equilibrium. - Xi Chen 001; Xiaotie Deng (FOCS, 2006)

Sparse Games Are Hard. - Xi Chen 001; Xiaotie Deng; Shang-Hua Teng (WINE, 2006)

Computing Nash Equilibria: Approximation and Smoothed Complexity. - Xi Chen 001; Xiaotie Deng; Shang-Hua Teng (Electron. Colloquium Comput. Complex., 2006)

Computing Exact p-Value for Structured Motif. - Jing Zhang 012; Xi Chen 001; Ming Li 001 (CPM, 2007)

Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. - Xi Chen 001; Shang-Hua Teng (FOCS, 2007)

The approximation complexity of win-lose games. - Xi Chen 001; Shang-Hua Teng; Paul Valiant (SODA, 2007)

Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation - Xi Chen 001; Shang-Hua Teng (CoRR, 2007)

Recent development in computational complexity characterization of Nash equilibrium. - Xi Chen 001; Xiaotie Deng (Comput. Sci. Rev., 2007)

On searching a table consistent with division poset. - Yongxi Cheng; Xi Chen 001; Yiqun Lisa Yin (Theor. Comput. Sci., 2007)

Complexity and approximation of the minimum recombinant haplotype configuration problem. - Lan Liu 001; Xi Chen 001; Jing Xiao; Tao Jiang 001 (Theor. Comput. Sci., 2007)

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. - Jin-yi Cai; Xi Chen 001; Dong Li (STOC, 2008)

Matching algorithmic bounds for finding a Brouwer fixed point. - Xi Chen 001; Xiaotie Deng (J. ACM, 2008)

Complexity of Bimatrix Nash Equilibria. - Xi Chen 001; Xiaotie Deng (Encyclopedia of Algorithms, 2008)

Incentive Compatible Selection. - Xi Chen 001; Xiaotie Deng (Encyclopedia of Algorithms, 2008)

Non-approximability of Bimatrix Nash Equilibria. - Xi Chen 001; Xiaotie Deng (Encyclopedia of Algorithms, 2008)

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. - Xi Chen 001; Decheng Dai; Ye Du; Shang-Hua Teng (FOCS, 2009)

Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. - Xi Chen 001; Shang-Hua Teng (ISAAC, 2009)

A Simplicial Approach for Discrete Fixed Point Theorems. - Xi Chen 001; Xiaotie Deng (Algorithmica, 2009)

Direct Sums in Randomized Communication Complexity. - Boaz Barak; Mark Braverman; Xi Chen 001; Anup Rao 001 (Electron. Colloquium Comput. Complex., 2009)

Settling the complexity of computing two-player Nash equilibria. - Xi Chen 001; Xiaotie Deng; Shang-Hua Teng (J. ACM, 2009)

On the complexity of 2D discrete fixed point problem. - Xi Chen 001; Xiaotie Deng (Theor. Comput. Sci., 2009)

Market equilibria with hybrid linear-Leontief utilities. - Xi Chen 001; Li-Sha Huang; Shang-Hua Teng (Theor. Comput. Sci., 2009)

On the complexity of equilibria in markets with additively separable utilities. - Xi Chen 001; Decheng Dai; Ye Du; Shang-Hua Teng (BQGT, 2010)

On Tractable Exponential Sums. - Jin-yi Cai; Xi Chen 001; Richard J. Lipton; Pinyan Lu (FAW, 2010)

Quantum Separation of Local Search and Fixed Point Computation. - Xi Chen 001; Xiaoming Sun 001; Shang-Hua Teng (Algorithmica, 2010)

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. - Jin-yi Cai; Xi Chen 001; Dong Li (Comput. Complex., 2010)

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy - Jin-yi Cai; Xi Chen 001; Pinyan Lu (CoRR, 2010)

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. - Jin-yi Cai; Xi Chen 001; Pinyan Lu (CCC, 2011)

A Complexity View of Markets with Social Influence. - Xi Chen 001; Shang-Hua Teng (ICS, 2011)

On Incentive Compatible Competitive Selection Protocols. - Xi Chen 001; Xiaotie Deng; Becky Jie Liu (Algorithmica, 2011)

Partial Derivatives in Arithmetic Complexity and Beyond. - Xi Chen 001; Neeraj Kayal; Avi Wigderson (Found. Trends Theor. Comput. Sci., 2011)

Guest column: complexity dichotomies of counting problems. - Xi Chen 001 (SIGACT News, 2011)

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. - Jin-Yi Cai; Xi Chen 001; Heng Guo 001; Pinyan Lu (COCOA, 2012)

Faster Canonical Forms for Strongly Regular Graphs. - László Babai; Xi Chen 001; Xiaorui Sun; Shang-Hua Teng; John Wilmes (FOCS, 2013)

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. - Xi Chen 001; Xiaorui Sun; Shang-Hua Teng (STOC, 2013)

How to Compress Interactive Communication. - Boaz Barak; Mark Braverman; Xi Chen 001; Anup Rao 001 (SIAM J. Comput., 2013)

Graph Homomorphisms with Complex Values: A Dichotomy Theorem. - Jin-Yi Cai; Xi Chen 001; Pinyan Lu (SIAM J. Comput., 2013)

New Algorithms and Lower Bounds for Monotonicity Testing. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan (FOCS, 2014)

The Complexity of Optimal Multidimensional Pricing. - Xi Chen 001; Ilias Diakonikolas; Dimitris Paparas; Xiaorui Sun; Mihalis Yannakakis (SODA, 2014)

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. - Xi Chen 001; Ilias Diakonikolas; Anthi Orfanou; Dimitris Paparas; Xiaorui Sun; Mihalis Yannakakis (FOCS, 2015)

On the Complexity of Nash Equilibria in Anonymous Games. - Xi Chen 001; David Durfee; Anthi Orfanou (STOC, 2015)

Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. - Xi Chen 001; Anindya De; Rocco A. Servedio; Li-Yang Tan (STOC, 2015)

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. - Xi Chen 001; Yu Cheng 002; Bo Tang (CoRR, 2015)

Addition is exponentially harder than counting for shallow monotone circuits. - Xi Chen 001; Igor Carboni Oliveira; Rocco A. Servedio (Electron. Colloquium Comput. Complex., 2015)

The complexity of approximating conservative counting CSPs. - Xi Chen 001; Martin E. Dyer; Leslie Ann Goldberg; Mark Jerrum; Pinyan Lu; Colin McQuillan; David Richerby (J. Comput. Syst. Sci., 2015)

On the Recursive Teaching Dimension of VC Classes. - Xi Chen 001; Yu Cheng 002; Bo Tang (NIPS, 2016)

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. - Xi Chen 001; Jinyu Xie (SODA, 2016)

Near-optimal small-depth lower bounds for small distance connectivity. - Xi Chen 001; Igor C. Oliveira 001; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

A Note on Teaching for VC Classes. - Xi Chen 001; Yu Cheng 002; Bo Tang (Electron. Colloquium Comput. Complex., 2016)

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. - Jin-Yi Cai; Xi Chen 001; Pinyan Lu (SIAM J. Comput., 2016)

Complexity Dichotomies for Counting Graph Homomorphisms. - Jin-Yi Cai; Xi Chen 001; Pinyan Lu (Encyclopedia of Algorithms, 2016)

Non-approximability of Bimatrix Nash Equilibria. - Xi Chen 001; Xiaotie Deng (Encyclopedia of Algorithms, 2016)

Sample-Based High-Dimensional Convexity Testing. - Xi Chen 001; Adam Freilich; Rocco A. Servedio; Timothy Sun (APPROX-RANDOM, 2017)

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan; Erik Waingarten (APPROX-RANDOM, 2017)

Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. - Xi Chen 001; Erik Waingarten; Jinyu Xie (FOCS, 2017)

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. - Xi Chen 001; Yu Cheng 002; Bo Tang (ITCS, 2017)

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. - Xi Chen 001; Erik Waingarten; Jinyu Xie (STOC, 2017)

On the Complexity of Bundle-Pricing and Simple Mechanisms. - Xi Chen 001; George Matikas; Dimitris Paparas; Mihalis Yannakakis (CoRR, 2017)

Settling the query complexity of non-adaptive junta testing. - Xi Chen 001; Rocco A. Servedio; Li-Yang Tan; Erik Waingarten; Jinyu Xie (Electron. Colloquium Comput. Complex., 2017)

Complexity of Counting CSP with Complex Weights. - Jin-Yi Cai; Xi Chen 001 (J. ACM, 2017)

The Complexity of Non-Monotone Markets. - Xi Chen 001; Dimitris Paparas; Mihalis Yannakakis (J. ACM, 2017)

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. - Xi Chen 001; George Matikas; Dimitris Paparas; Mihalis Yannakakis (SODA, 2018)

The complexity of optimal multidimensional pricing for a unit-demand buyer. - Xi Chen 001; Ilias Diakonikolas; Dimitris Paparas; Xiaorui Sun; Mihalis Yannakakis (Games Econ. Behav., 2018)

An Axiomatic Approach to Block Rewards. - Xi Chen 001; Christos H. Papadimitriou; Tim Roughgarden (AFT, 2019)

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. - Frank Ban; Xi Chen 001; Rocco A. Servedio; Sandip Sinha (APPROX-RANDOM, 2019)

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. - Frank Ban; Xi Chen 001; Adam Freilich; Rocco A. Servedio; Sandip Sinha (FOCS, 2019)

Detecting Customer Complaint Escalation with Recurrent Neural Networks and Manually-Engineered Features. - Wei Yang 017; Luchen Tan; Chunwei Lu; Anqi Cui; Han Li; Xi Chen 001; Kun Xiong; Muzi Wang; Ming Li 001; Jian Pei 001; Jimmy Lin (NAACL-HLT (2), 2019)

Testing unateness nearly optimally. - Xi Chen 001; Erik Waingarten (STOC, 2019)

A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. - Jin-Yi Cai; Xi Chen 001 (Comput. Complex., 2019)

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. - Clément L. Canonne; Xi Chen 001; Gautam Kamath 001; Amit Levi; Erik Waingarten (Electron. Colloquium Comput. Complex., 2019)

Distribution-free Junta Testing. - Zhengyang Liu 002; Xi Chen 001; Rocco A. Servedio; Ying Sheng 004; Jinyu Xie (ACM Trans. Algorithms, 2019)

Hedging in games: Faster convergence of external and swap regrets. - Xi Chen 001; Binghui Peng (NeurIPS, 2020)

Nearly optimal edge estimation with independent set queries. - Xi Chen 001; Amit Levi; Erik Waingarten (SODA, 2020)

Smoothed complexity of local max-cut and binary max-CSP. - Xi Chen 001; Chenghao Guo; Emmanouil V. Vlatakis-Gkaragkounis; Mihalis Yannakakis; Xinzhi Zhang 002 (STOC, 2020)

Learning and Testing Junta Distributions with Subcube Conditioning. - Xi Chen 001; Rajesh Jayaram; Amit Levi; Erik Waingarten (CoRR, 2020)

Learning and testing junta distributions with sub cube conditioning. - Xi Chen 001; Rajesh Jayaram; Amit Levi; Erik Waingarten (COLT, 2021)

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. - Xi Chen 001; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha (ITCS, 2021)

Throttling Equilibria in Auction Markets. - Xi Chen 001; Christian Kroer; Rachitesh Kumar (WINE, 2021)

Memory Bounds for Continual Learning. - Xi Chen 001; Christos H. Papadimitriou; Binghui Peng (FOCS, 2022)

Improved Upper Bounds for Finding Tarski Fixed Points. - Xi Chen 001; Yuhao Li 002 (EC, 2022)

Computational Hardness of the Hylland-Zeckhauser Scheme. - Thomas Chen; Xi Chen 001; Binghui Peng; Mihalis Yannakakis (SODA, 2022)

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. - Xi Chen 001; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha (SODA, 2022)

Average-Case Subset Balancing Problems. - Xi Chen 001; Yaonan Jin; Tim Randolph 001; Rocco A. Servedio (SODA, 2022)

New streaming algorithms for high dimensional EMD and MST. - Xi Chen 001; Rajesh Jayaram; Amit Levi; Erik Waingarten (STOC, 2022)

On the complexity of dynamic submodular maximization. - Xi Chen 001; Binghui Peng (STOC, 2022)

SoK: Play-to-Earn Projects. - Jingfan Yu; Mengqian Zhang; Xi Chen 001; Zhixuan Fang (CoRR, 2022)

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer. - Xi Chen 001; Ilias Diakonikolas; Anthi Orfanou; Dimitris Paparas; Xiaorui Sun; Mihalis Yannakakis (SIAM J. Comput., 2022)

A Lower Bound on Cycle-Finding in Sparse Digraphs. - Xi Chen 001; Tim Randolph 001; Rocco A. Servedio; Timothy Sun (ACM Trans. Algorithms, 2022)

Subset Sum in Time 2n/2 / poly(n). - Xi Chen 001; Yaonan Jin; Tim Randolph 001; Rocco A. Servedio (APPROX/RANDOM, 2023)

Approximate Trace Reconstruction from a Single Trace. - Xi Chen 001; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha (SODA, 2023)

Streaming Euclidean MST to a Constant Factor. - Xi Chen 001; Vincent Cohen-Addad; Rajesh Jayaram; Amit Levi; Erik Waingarten (STOC, 2023)

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules. - Xi Chen 001; Binghui Peng (STOC, 2023)

Memory-Query Tradeoffs for Randomized Convex Optimization. - Xi Chen 001; Binghui Peng (CoRR, 2023)

Reducing Tarski to Unique Tarski (in the Black-box Model). - Xi Chen 001; Yuhao Li 002; Mihalis Yannakakis (Electron. Colloquium Comput. Complex., 2023)

Trace Reconstruction from Local Statistical Queries. - Xi Chen 001; Anindya De; Chin Ho Lee; Rocco A. Servedio (APPROX/RANDOM, 2024)

Testing Intersecting and Union-Closed Families. - Xi Chen 001; Anindya De; Yuhao Li 002; Shivam Nadimpalli; Rocco A. Servedio (ITCS, 2024)

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. - Xi Chen 001; Anindya De; Yuhao Li 002; Shivam Nadimpalli; Rocco A. Servedio (SODA, 2024)

Smoothed Complexity of SWAP in Local Graph Partitioning. - Xi Chen 001; Chenghao Guo; Emmanouil V. Vlatakis-Gkaragkounis; Mihalis Yannakakis (SODA, 2024)

Uniformity Testing over Hypergrids with Subcube Conditioning. - Xi Chen 001; Cassandra Marcussen (SODA, 2024)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries. - Xi Chen 001; Yumou Fei; Shyamal Patel (STOC, 2024)

Testing Sumsets is Hard. - Xi Chen 001; Shivam Nadimpalli; Tim Randolph 001; Rocco A. Servedio; Or Zamir (CoRR, 2024)

Computing a Fixed Point of Contraction Maps in Polynomial Queries. - Xi Chen 001; Yuhao Li 002; Mihalis Yannakakis (Electron. Colloquium Comput. Complex., 2024)

The Complexity of Pacing for Second-Price Auctions. - Xi Chen 001; Christian Kroer; Rachitesh Kumar (Math. Oper. Res., 2024)

Testing Juntas and Junta Subclasses with Relative Error. - Xi Chen 001; William Pires; Toniann Pitassi; Rocco A. Servedio (COLT, 2025)

Relative-Error Testing of Conjunctions and Decision Lists. - Xi Chen 001; William Pires; Toniann Pitassi; Rocco A. Servedio (ICALP, 2025)

Relative-error monotonicity testing. - Xi Chen 001; Anindya De; Yizhi Huang; Yuhao Li 002; Shivam Nadimpalli; Rocco A. Servedio; Tianqi Yang (SODA, 2025)

Lower Bounds for Convexity Testing. - Xi Chen 001; Anindya De; Shivam Nadimpalli; Rocco A. Servedio; Erik Waingarten (SODA, 2025)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning. - Deeparnab Chakrabarty; Xi Chen 001; Simeon Ristic; C. Seshadhri 001; Erik Waingarten (STOC, 2025)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions. - Xi Chen 001; Shyamal Patel; Rocco A. Servedio (CoRR, 2025)

Polynomial-time Trace Reconstruction in the Smoothed Complexity Model. - Xi Chen 001; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha (ACM Trans. Algorithms, 2025)