Xi Chen

209 papers A* 56A 12B 4C 2Misc 4Journal 115Unranked 11
YearRankTypeTitle / Venue / Authors
2026 J jnl
DNF formulas are efficiently testable with relative error.
CoRR
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2026 A* conf
Halfspaces are hard to test with relative error.
SODA
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2026 J jnl
Quadratic Speedup for Computing Contraction Fixed Points.
CoRR
Xi Chen, Yuhao Li, Mihalis Yannakakis
2026 J jnl
Reducing Tarski to Unique Tarski (In the Black-Box Model).
SIAM J. Comput.
Xi Chen, Yuhao Li, Mihalis Yannakakis
2026 A conf
Semi-Random Graphs, Robust Asymmetry, and Reconstruction.
ITCS
Julian Asilis, Xi Chen, Dutch Hansen, Shang-Hua Teng
2025 J jnl
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions.
CoRR
Xi Chen, Shyamal Patel, Rocco A. Servedio
2025 J jnl
Computing a Fixed Point of Contraction Maps in Polynomial Queries.
J. ACM
Xi Chen, Yuhao Li, Mihalis Yannakakis
2025 J jnl
Halfspaces are hard to test with relative error.
CoRR
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025 A* conf
Lower Bounds for Convexity Testing.
SODA
Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2025 J jnl
Model-agnostic super-resolution in high dimensions.
CoRR
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025 A* conf
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning.
STOC
Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten
2025 J jnl
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning.
CoRR
Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten
2025 J jnl
Polynomial-time Trace Reconstruction in the Smoothed Complexity Model.
ACM Trans. Algorithms
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2025 A* conf
Relative-Error Testing of Conjunctions and Decision Lists.
ICALP
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025 A* conf
Relative-error monotonicity testing.
SODA
Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025 J jnl
Relative-error testing of conjunctions and decision lists.
CoRR
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025 J jnl
Relative-error unateness testing.
CoRR
Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, Yiding Zhang
2025 J jnl
Semi-Random Graphs, Robust Asymmetry, and Reconstruction.
CoRR
Julian Asilis, Xi Chen, Dutch Hansen, Shang-Hua Teng
2025 A* conf
Testing Juntas and Junta Subclasses with Relative Error.
COLT
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025 J jnl
Testing Juntas and Junta Subclasses with Relative Error.
CoRR
Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025 A conf
Testing Sumsets Is Hard.
ESA
Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2024 A* conf
Computing a Fixed Point of Contraction Maps in Polynomial Queries.
STOC
Xi Chen, Yuhao Li, Mihalis Yannakakis
2024 J jnl
Computing a Fixed Point of Contraction Maps in Polynomial Queries.
CoRR
Xi Chen, Yuhao Li, Mihalis Yannakakis
2024 J jnl
Computing a Fixed Point of Contraction Maps in Polynomial Queries.
Electron. Colloquium Comput. Complex.
Xi Chen, Yuhao Li, Mihalis Yannakakis
2024 A* conf
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries.
STOC
Xi Chen, Yumou Fei, Shyamal Patel
2024 J jnl
Lower Bounds for Convexity Testing.
CoRR
Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2024 A* conf
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.
SODA
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024 J jnl
Relative-error monotonicity testing.
CoRR
Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2024 A* conf
Smoothed Complexity of SWAP in Local Graph Partitioning.
SODA
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis
2024 A conf
Testing Intersecting and Union-Closed Families.
ITCS
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024 J jnl
Testing Sumsets is Hard.
CoRR
Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2024 J jnl
The Complexity of Pacing for Second-Price Auctions.
Math. Oper. Res.
Xi Chen, Christian Kroer, Rachitesh Kumar
2024 A conf
Trace Reconstruction from Local Statistical Queries.
APPROX/RANDOM
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
2024 J jnl
Trace reconstruction from local statistical queries.
CoRR
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
2024 A* conf
Uniformity Testing over Hypergrids with Subcube Conditioning.
SODA
Xi Chen, Cassandra Marcussen
2023 A* conf
Approximate Trace Reconstruction from a Single Trace.
SODA
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2023 A* conf
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.
STOC
Xi Chen, Binghui Peng
2023 J jnl
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.
CoRR
Xi Chen, Binghui Peng
2023 J jnl
Memory-Query Tradeoffs for Randomized Convex Optimization.
CoRR
Xi Chen, Binghui Peng
2023 J jnl
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.
CoRR
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2023 A conf
Reducing Tarski to Unique Tarski (In the Black-Box Model).
CCC
Xi Chen, Yuhao Li, Mihalis Yannakakis
2023 J jnl
Reducing Tarski to Unique Tarski (in the Black-box Model).
Electron. Colloquium Comput. Complex.
Xi Chen, Yuhao Li, Mihalis Yannakakis
2023 J jnl
Smoothed Complexity of SWAP in Local Graph Partitioning.
CoRR
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis
2023 A* conf
Streaming Euclidean MST to a Constant Factor.
STOC
Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten
2023 A conf
Subset Sum in Time 2
APPROX/RANDOM
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2023 J jnl
Subset Sum in Time 2
CoRR
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2023 J jnl
Testing Intersecting and Union-Closed Families.
CoRR
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2022 J jnl
A Lower Bound on Cycle-Finding in Sparse Digraphs.
ACM Trans. Algorithms
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2022 J jnl
Approximate Trace Reconstruction from a Single Trace.
CoRR
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2022 A* conf
Average-Case Subset Balancing Problems.
SODA
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2022 A* conf
Computational Hardness of the Hylland-Zeckhauser Scheme.
SODA
Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis
2022 A* conf
Improved Upper Bounds for Finding Tarski Fixed Points.
EC
Xi Chen, Yuhao Li
2022 J jnl
Improved Upper Bounds for Finding Tarski Fixed Points.
CoRR
Xi Chen, Yuhao Li
2022 A* conf
Memory Bounds for Continual Learning.
FOCS
Xi Chen, Christos H. Papadimitriou, Binghui Peng
2022 J jnl
Memory Bounds for Continual Learning.
CoRR
Xi Chen, Christos H. Papadimitriou, Binghui Peng
2022 A* conf
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.
SODA
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2022 A* conf
New streaming algorithms for high dimensional EMD and MST.
STOC
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2022 J jnl
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.
SIAM J. Comput.
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
2022 A* conf
On the complexity of dynamic submodular maximization.
STOC
Xi Chen, Binghui Peng
2022 J jnl
SoK: Play-to-Earn Projects.
CoRR
Jingfan Yu, Mengqian Zhang, Xi Chen, Zhixuan Fang
2022 J jnl
Streaming Euclidean MST to a Constant Factor.
CoRR
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2021 J jnl
Average-Case Subset Balancing Problems.
CoRR
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2021 J jnl
Computational Hardness of the Hylland-Zeckhauser Scheme.
CoRR
Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis
2021 A* conf
Learning and testing junta distributions with sub cube conditioning.
COLT
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2021 J jnl
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.
CoRR
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021 J jnl
New Streaming Algorithms for High Dimensional EMD and MST.
CoRR
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2021 J jnl
On the Complexity of Dynamic Submodular Maximization.
CoRR
Xi Chen, Binghui Peng
2021 A conf
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.
ITCS
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021 A* conf
Polynomial-time trace reconstruction in the smoothed complexity model.
SODA
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021 A* conf
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
SODA
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2021 A* conf
The Complexity of Pacing for Second-Price Auctions.
EC
Xi Chen, Christian Kroer, Rachitesh Kumar
2021 J jnl
The Complexity of Pacing for Second-Price Auctions.
CoRR
Xi Chen, Christian Kroer, Rachitesh Kumar
2021 — conf
Throttling Equilibria in Auction Markets.
WINE
Xi Chen, Christian Kroer, Rachitesh Kumar
2021 J jnl
Throttling Equilibria in Auction Markets.
CoRR
Xi Chen, Christian Kroer, Rachitesh Kumar
2020 A* conf
A Lower Bound on Cycle-Finding in Sparse Digraphs.
SODA
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2020 A* conf
Hedging in games: Faster convergence of external and swap regrets.
NeurIPS
Xi Chen, Binghui Peng
2020 J jnl
Hedging in games: Faster convergence of external and swap regrets.
CoRR
Xi Chen, Binghui Peng
2020 J jnl
Learning and Testing Junta Distributions with Subcube Conditioning.
CoRR
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2020 A* conf
Nearly optimal edge estimation with independent set queries.
SODA
Xi Chen, Amit Levi, Erik Waingarten
2020 J jnl
Polynomial-time trace reconstruction in the low deletion rate regime.
CoRR
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2020 J jnl
Polynomial-time trace reconstruction in the smoothed complexity model.
CoRR
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2020 A* conf
Smoothed complexity of local max-cut and binary max-CSP.
STOC
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
2019 J jnl
A Lower Bound on Cycle-Finding in Sparse Digraphs.
CoRR
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2019 J jnl
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.
Comput. Complex.
Jin-Yi Cai, Xi Chen
2019 B conf
An Axiomatic Approach to Block Rewards.
AFT
Xi Chen, Christos H. Papadimitriou, Tim Roughgarden
2019 J jnl
An Axiomatic Approach to Block Rewards.
CoRR
Xi Chen, Christos H. Papadimitriou, Tim Roughgarden
2019 A* conf
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.
FOCS
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
2019 J jnl
Beyond trace reconstruction: Population recovery from the deletion channel.
CoRR
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
2019 — conf
Detecting Customer Complaint Escalation with Recurrent Neural Networks and Manually-Engineered Features.
NAACL-HLT (2)
Wei Yang, Luchen Tan, Chunwei Lu, Anqi Cui, Han Li, Xi Chen, Kun Xiong, Muzi Wang, Ming Li, Jian Pei, Jimmy Lin
2019 J jnl
Distribution-free Junta Testing.
ACM Trans. Algorithms
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2019 — conf
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.
APPROX-RANDOM
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
2019 J jnl
Efficient average-case population recovery in the presence of insertions and deletions.
CoRR
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
2019 J jnl
Nearly optimal edge estimation with independent set queries.
CoRR
Xi Chen, Amit Levi, Erik Waingarten
2019 J jnl
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
CoRR
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2019 J jnl
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Electron. Colloquium Comput. Complex.
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2019 J jnl
Smoothed complexity of local Max-Cut and binary Max-CSP.
CoRR
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
2019 J jnl
Testing Unateness Nearly Optimally.
CoRR
Xi Chen, Erik Waingarten
2019 A* conf
Testing unateness nearly optimally.
STOC
Xi Chen, Erik Waingarten
2018 J jnl
Distribution-free Junta Testing.
CoRR
Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2018 A* conf
Distribution-free junta testing.
STOC
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2018 A* conf
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.
SODA
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
2018 J jnl
Settling the Query Complexity of Non-adaptive Junta Testing.
J. ACM
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2018 J jnl
The complexity of optimal multidimensional pricing for a unit-demand buyer.
Games Econ. Behav.
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
2017 — conf
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
APPROX-RANDOM
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017 J jnl
Adaptivity is exponentially powerful for testing monotonicity of halfspaces.
CoRR
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017 A* conf
Addition is exponentially harder than counting for shallow monotone circuits.
STOC
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2017 J jnl
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness.
CoRR
Xi Chen, Erik Waingarten, Jinyu Xie
2017 A* conf
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.
STOC
Xi Chen, Erik Waingarten, Jinyu Xie
2017 J jnl
Boolean Unateness Testing with Õ(n
CoRR
Xi Chen, Erik Waingarten, Jinyu Xie
2017 A* conf
Boolean Unateness Testing with Õ(n
FOCS
Xi Chen, Erik Waingarten, Jinyu Xie
2017 J jnl
Complexity of Counting CSP with Complex Weights.
J. ACM
Jin-Yi Cai, Xi Chen
2017 J jnl
On the Complexity of Bundle-Pricing and Simple Mechanisms.
CoRR
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
2017 — conf
Sample-Based High-Dimensional Convexity Testing.
APPROX-RANDOM
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
2017 J jnl
Sample-based high-dimensional convexity testing.
CoRR
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
2017 A conf
Settling the Query Complexity of Non-Adaptive Junta Testing.
CCC
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017 J jnl
Settling the query complexity of non-adaptive junta testing.
CoRR
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017 J jnl
Settling the query complexity of non-adaptive junta testing.
Electron. Colloquium Comput. Complex.
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017 J jnl
The Complexity of Non-Monotone Markets.
J. ACM
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
2017 A conf
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games.
ITCS
Xi Chen, Yu Cheng, Bo Tang
2016 J jnl
A Note on Teaching for VC Classes.
Electron. Colloquium Comput. Complex.
Xi Chen, Yu Cheng, Bo Tang
2016 — ch.
Complexity Dichotomies for Counting Graph Homomorphisms.
Encyclopedia of Algorithms
Jin-Yi Cai, Xi Chen, Pinyan Lu
2016 A* conf
Near-optimal small-depth lower bounds for small distance connectivity.
STOC
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2016 — ch.
Non-approximability of Bimatrix Nash Equilibria.
Encyclopedia of Algorithms
Xi Chen, Xiaotie Deng
2016 J jnl
Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.
SIAM J. Comput.
Jin-Yi Cai, Xi Chen, Pinyan Lu
2016 — conf
On the Recursive Teaching Dimension of VC Classes.
NIPS
Xi Chen, Yu Cheng, Bo Tang
2016 A* conf
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.
SODA
Xi Chen, Jinyu Xie
2015 J jnl
Addition is exponentially harder than counting for shallow monotone circuits.
CoRR
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2015 J jnl
Addition is exponentially harder than counting for shallow monotone circuits.
Electron. Colloquium Comput. Complex.
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
2015 A* conf
Boolean Function Monotonicity Testing Requires (Almost) n
STOC
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
2015 J jnl
Near-optimal small-depth lower bounds for small distance connectivity.
CoRR
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015 A* conf
On the Complexity of Nash Equilibria in Anonymous Games.
STOC
Xi Chen, David Durfee, Anthi Orfanou
2015 A* conf
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.
FOCS
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
2015 J jnl
The complexity of approximating conservative counting CSPs.
J. Comput. Syst. Sci.
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
2015 J jnl
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.
CoRR
Xi Chen, Jinyu Xie
2015 J jnl
Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games.
CoRR
Xi Chen, Yu Cheng, Bo Tang
2014 J jnl
Boolean function monotonicity testing requires (almost) n
CoRR
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
2014 A* conf
New Algorithms and Lower Bounds for Monotonicity Testing.
FOCS
Xi Chen, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
New algorithms and lower bounds for monotonicity testing.
CoRR
Xi Chen, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
On the Complexity of Nash Equilibria in Anonymous Games.
CoRR
Xi Chen, David Durfee, Anthi Orfanou
2014 A* conf
The Complexity of Optimal Multidimensional Pricing.
SODA
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
2013 A* conf
Faster Canonical Forms for Strongly Regular Graphs.
FOCS
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
2013 J jnl
Graph Homomorphisms with Complex Values: A Dichotomy Theorem.
SIAM J. Comput.
Jin-Yi Cai, Xi Chen, Pinyan Lu
2013 J jnl
How to Compress Interactive Communication.
SIAM J. Comput.
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2013 A* conf
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems.
STOC
Xi Chen, Xiaorui Sun, Shang-Hua Teng
2013 J jnl
The Complexity of Optimal Multidimensional Pricing.
CoRR
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
2013 A conf
The complexity of approximating conservative counting CSPs.
STACS
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
2013 A* conf
The complexity of non-monotone markets.
STOC
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
2012 A* conf
Complexity of counting CSP with complex weights.
STOC
Jin-Yi Cai, Xi Chen
2012 J jnl
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems
CoRR
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
2012 C conf
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.
COCOA
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
2012 J jnl
The Complexity of Non-Monotone Markets
CoRR
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
2012 J jnl
The complexity of approximating conservative counting CSPs
CoRR
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
2011 A conf
A Complexity View of Markets with Social Influence.
ICS
Xi Chen, Shang-Hua Teng
2011 J jnl
Complexity of Counting CSP with Complex Weights
CoRR
Jin-Yi Cai, Xi Chen
2011 J jnl
Guest column: complexity dichotomies of counting problems.
SIGACT News
Xi Chen
2011 A conf
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.
CCC
Jin-Yi Cai, Xi Chen, Pinyan Lu
2011 J jnl
On Incentive Compatible Competitive Selection Protocols.
Algorithmica
Xi Chen, Xiaotie Deng, Becky Jie Liu
2011 J jnl
Partial Derivatives in Arithmetic Complexity and Beyond.
Found. Trends Theor. Comput. Sci.
Xi Chen, Neeraj Kayal, Avi Wigderson
2010 J jnl
A Complexity View of Markets with Social Influence
CoRR
Xi Chen, Shang-Hua Teng
2010 J jnl
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
CoRR
Jin-Yi Cai, Xi Chen
2010 A* conf
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights.
FOCS
Jin-Yi Cai, Xi Chen
2010 — conf
Graph Homomorphisms with Complex Values: A Dichotomy Theorem.
ICALP (1)
Jin-Yi Cai, Xi Chen, Pinyan Lu
2010 A* conf
How to compress interactive communication.
STOC
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2010 J jnl
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy
CoRR
Jin-Yi Cai, Xi Chen, Pinyan Lu
2010 J jnl
On Tractable Exponential Sums
CoRR
Jin-Yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu
2010 Misc conf
On Tractable Exponential Sums.
FAW
Jin-Yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu
2010 — conf
On the complexity of equilibria in markets with additively separable utilities.
BQGT
Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng
2010 J jnl
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.
Comput. Complex.
Jin-Yi Cai, Xi Chen, Dong Li
2010 J jnl
Quantum Separation of Local Search and Fixed Point Computation.
Algorithmica
Xi Chen, Xiaoming Sun, Shang-Hua Teng
2009 J jnl
A Simplicial Approach for Discrete Fixed Point Theorems.
Algorithmica
Xi Chen, Xiaotie Deng
2009 J jnl
Direct Sums in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex.
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
2009 J jnl
Graph Homomorphisms with Complex Values: A Dichotomy Theorem
CoRR
Jin-Yi Cai, Xi Chen, Pinyan Lu
2009 J jnl
Market equilibria with hybrid linear-Leontief utilities.
Theor. Comput. Sci.
Xi Chen, Li-Sha Huang, Shang-Hua Teng
2009 J jnl
On the complexity of 2D discrete fixed point problem.
Theor. Comput. Sci.
Xi Chen, Xiaotie Deng
2009 J jnl
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
CoRR
Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng
2009 A* conf
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.
FOCS
Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng
2009 J jnl
Settling the complexity of computing two-player Nash equilibria.
J. ACM
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2009 B conf
Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.
ISAAC
Xi Chen, Shang-Hua Teng
2009 J jnl
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
CoRR
Xi Chen, Shang-Hua Teng
2008 A* conf
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.
STOC
Jin-Yi Cai, Xi Chen, Dong Li
2008 — ch.
Complexity of Bimatrix Nash Equilibria.
Encyclopedia of Algorithms
Xi Chen, Xiaotie Deng
2008 — ch.
Incentive Compatible Selection.
Encyclopedia of Algorithms
Xi Chen, Xiaotie Deng
2008 J jnl
Matching algorithmic bounds for finding a Brouwer fixed point.
J. ACM
Xi Chen, Xiaotie Deng
2008 — ch.
Non-approximability of Bimatrix Nash Equilibria.
Encyclopedia of Algorithms
Xi Chen, Xiaotie Deng
2008 Misc conf
Quantum Separation of Local Search and Fixed Point Computation.
COCOON
Xi Chen, Xiaoming Sun, Shang-Hua Teng
2007 J jnl
Complexity and approximation of the minimum recombinant haplotype configuration problem.
Theor. Comput. Sci.
Lan Liu, Xi Chen, Jing Xiao, Tao Jiang
2007 B conf
Computing Exact p-Value for Structured Motif.
CPM
Jing Zhang, Xi Chen, Ming Li
2007 J jnl
On searching a table consistent with division poset.
Theor. Comput. Sci.
Yongxi Cheng, Xi Chen, Yiqun Lisa Yin
2007 J jnl
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
CoRR
Xi Chen, Shang-Hua Teng
2007 A* conf
Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation.
FOCS
Xi Chen, Shang-Hua Teng
2007 J jnl
Recent development in computational complexity characterization of Nash equilibrium.
Comput. Sci. Rev.
Xi Chen, Xiaotie Deng
2007 J jnl
Settling the Complexity of Computing Two-Player Nash Equilibria
CoRR
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2007 A* conf
The approximation complexity of win-lose games.
SODA
Xi Chen, Shang-Hua Teng, Paul Valiant
2006 Misc conf
A Simplicial Approach for Discrete Fixed Point Theorems.
COCOON
Xi Chen, Xiaotie Deng
2006 J jnl
Computing Nash Equilibria: Approximation and Smoothed Complexity
CoRR
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2006 A* conf
Computing Nash Equilibria: Approximation and Smoothed Complexity.
FOCS
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2006 J jnl
Computing Nash Equilibria: Approximation and Smoothed Complexity.
Electron. Colloquium Comput. Complex.
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2006 C conf
Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set.
AAIM
Xi Chen, Xiaotie Deng
2006 — conf
Market Equilibria with Hybrid Linear-Leontief Utilities.
WINE
Xi Chen, Li-Sha Huang, Shang-Hua Teng
2006 Misc conf
On Incentive Compatible Competitive Selection Protocol.
COCOON
Xi Chen, Xiaotie Deng, Becky Jie Liu
2006 — conf
On the Complexity of 2D Discrete Fixed Point Problem.
ICALP (1)
Xi Chen, Xiaotie Deng
2006 J jnl
On the Complexity of 2D Discrete Fixed Point Problem.
Electron. Colloquium Comput. Complex.
Xi Chen, Xiaotie Deng
2006 A* conf
Settling the Complexity of Two-Player Nash Equilibrium.
FOCS
Xi Chen, Xiaotie Deng
2006 — conf
Sparse Games Are Hard.
WINE
Xi Chen, Xiaotie Deng, Shang-Hua Teng
2005 J jnl
3-NASH is PPAD-Complete
Electron. Colloquium Comput. Complex.
Xi Chen, Xiaotie Deng
2005 B conf
Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.
ISAAC
Lan Liu, Xi Chen, Jing Xiao, Tao Jiang
2005 J jnl
On Searching a Table Consistent with Division Poset
CoRR
Yongxi Cheng, Xi Chen, Yiqun Lisa Yin
2005 A* conf
On algorithms for discrete and approximate brouwer fixed points.
STOC
Xi Chen, Xiaotie Deng
2005 J jnl
Settling the Complexity of 2-Player Nash-Equilibrium
Electron. Colloquium Comput. Complex.
Xi Chen, Xiaotie Deng