Xi Chen

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 76

Top Venues

CoRR

SODA

STOC

Electron. Colloquium Comput. Complex.

Publications

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Testing Intersecting and Union-Closed Families. ITCS (2024)
Xi Chen, Cassandra Marcussen
Uniformity Testing over Hypergrids with Subcube Conditioning. SODA (2024)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Computing a Fixed Point of Contraction Maps in Polynomial Queries. Electron. Colloquium Comput. Complex. (2024)
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis
Smoothed Complexity of SWAP in Local Graph Partitioning. SODA (2024)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA (2024)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
Trace reconstruction from local statistical queries. CoRR (2024)
Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
Testing Sumsets is Hard. CoRR (2024)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
/ poly(n). APPROX/RANDOM (2023)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis
Smoothed Complexity of SWAP in Local Graph Partitioning. CoRR (2023)
Xi Chen, Yuhao Li, Mihalis Yannakakis
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC (2023)
Xi Chen, Binghui Peng
Memory-Query Tradeoffs for Randomized Convex Optimization. CoRR (2023)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Testing Intersecting and Union-Closed Families. CoRR (2023)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR (2023)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Approximate Trace Reconstruction from a Single Trace. SODA (2023)
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer. SIAM J. Comput. 51 (3) (2022)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms 18 (4) (2022)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
Average-Case Subset Balancing Problems. SODA (2022)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. SODA (2022)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. CoRR (2021)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
Average-Case Subset Balancing Problems. CoRR (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the smoothed complexity model. SODA (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. ITCS (2021)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. SODA (2021)
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
Learning and Testing Junta Distributions with Subcube Conditioning. CoRR (2020)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the low deletion rate regime. CoRR (2020)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the smoothed complexity model. CoRR (2020)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. SODA (2020)
Xi Chen, Amit Levi, Erik Waingarten
Nearly optimal edge estimation with independent set queries. SODA (2020)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
Smoothed complexity of local max-cut and binary max-CSP. STOC (2020)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. CoRR (2019)
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. APPROX-RANDOM (2019)
Xi Chen, Erik Waingarten
Testing Unateness Nearly Optimally. CoRR (2019)
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang
Smoothed complexity of local Max-Cut and binary Max-CSP. CoRR (2019)
Xi Chen, Erik Waingarten
Testing unateness nearly optimally. STOC (2019)
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
Beyond trace reconstruction: Population recovery from the deletion channel. CoRR (2019)
Xi Chen, Amit Levi, Erik Waingarten
Nearly optimal edge estimation with independent set queries. CoRR (2019)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. CoRR (2019)
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free Junta Testing. ACM Trans. Algorithms 15 (1) (2019)
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. FOCS (2019)
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
Efficient average-case population recovery in the presence of insertions and deletions. CoRR (2019)
Jin-Yi Cai, Xi Chen
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Comput. Complex. 28 (3) (2019)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Electron. Colloquium Comput. Complex. 26 (2019)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65 (6) (2018)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The complexity of optimal multidimensional pricing for a unit-demand buyer. Games Econ. Behav. 110 (2018)
Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free Junta Testing. CoRR (2018)
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free junta testing. STOC (2018)
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. SODA (2018)
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. 24 (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-Adaptive Junta Testing. Computational Complexity Conference (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. STOC (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
) Adaptive Queries. FOCS (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness. CoRR (2017)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The Complexity of Non-Monotone Markets. J. ACM 64 (3) (2017)
Xi Chen, Yu Cheng, Bo Tang
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. ITCS (2017)
Jin-Yi Cai, Xi Chen
Complexity of Counting CSP with Complex Weights. J. ACM 64 (3) (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
) Adaptive Queries. CoRR (2017)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. STOC (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM (2017)
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
Sample-based high-dimensional convexity testing. CoRR (2017)
Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis
On the Complexity of Bundle-Pricing and Simple Mechanisms. CoRR (2017)
Xi Chen, Yu Cheng, Bo Tang
On the Recursive Teaching Dimension of VC Classes. NIPS (2016)
Xi Chen, Jinyu Xie
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. SODA (2016)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Near-optimal small-depth lower bounds for small distance connectivity. STOC (2016)
Jin-Yi Cai, Xi Chen, Pinyan Lu
Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. SIAM J. Comput. 45 (6) (2016)
Xi Chen, Yu Cheng, Bo Tang
A Note on Teaching for VC Classes. Electron. Colloquium Comput. Complex. 23 (2016)
Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. FOCS (2015)
Xi Chen, Jinyu Xie
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. CoRR (2015)
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
Non-adaptive Queries. STOC (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. CoRR (2015)
Xi Chen, David Durfee, Anthi Orfanou
On the Complexity of Nash Equilibria in Anonymous Games. STOC (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Near-optimal small-depth lower bounds for small distance connectivity. CoRR (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Xi Chen, Yu Cheng, Bo Tang
Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. CoRR (2015)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The Complexity of Optimal Multidimensional Pricing. SODA (2014)
Xi Chen, Rocco A. Servedio, Li-Yang Tan
New Algorithms and Lower Bounds for Monotonicity Testing. FOCS (2014)
Xi Chen, David Durfee, Anthi Orfanou
On the Complexity of Nash Equilibria in Anonymous Games. CoRR (2014)
Xi Chen, Rocco A. Servedio, Li-Yang Tan
New algorithms and lower bounds for monotonicity testing. CoRR (2014)
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
non-adaptive queries. CoRR (2014)
Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
The Complexity of Optimal Multidimensional Pricing. CoRR (2013)
Jin-Yi Cai, Xi Chen, Pinyan Lu
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. SIAM J. Comput. 42 (3) (2013)
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
How to Compress Interactive Communication. SIAM J. Comput. 42 (3) (2013)
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
Faster Canonical Forms for Strongly Regular Graphs. FOCS (2013)
Xi Chen, Xiaorui Sun, Shang-Hua Teng
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. STOC (2013)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The complexity of non-monotone markets. STOC (2013)
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA (2012)
Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems CoRR (2012)
Jin-Yi Cai, Xi Chen
Complexity of counting CSP with complex weights. STOC (2012)
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
The Complexity of Non-Monotone Markets CoRR (2012)
Xi Chen, Xiaotie Deng, Becky Jie Liu
On Incentive Compatible Competitive Selection Protocols. Algorithmica 61 (2) (2011)
Xi Chen
Guest column: complexity dichotomies of counting problems. SIGACT News 42 (4) (2011)
Jin-yi Cai, Xi Chen, Pinyan Lu
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. Computational Complexity Conference (2011)
Jin-yi Cai, Xi Chen
Complexity of Counting CSP with Complex Weights CoRR (2011)
Xi Chen, Neeraj Kayal, Avi Wigderson
Partial Derivatives in Arithmetic Complexity and Beyond. Found. Trends Theor. Comput. Sci. 6 (1-2) (2011)
Xi Chen, Shang-Hua Teng
A Complexity View of Markets with Social Influence. ICS (2011)
Jin-yi Cai, Xi Chen, Pinyan Lu
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy CoRR (2010)
Jin-yi Cai, Xi Chen
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. FOCS (2010)
Xi Chen, Xiaoming Sun, Shang-Hua Teng
Quantum Separation of Local Search and Fixed Point Computation. Algorithmica 56 (3) (2010)

Xi Chen.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Xi Chen