Xi Chen

Orcid: 0000-0001-5661-515X

Affiliations:
  • Columbia University, New York City, NY, USA
  • Princeton University, NJ, USA (former)
  • University of Southern California, Los Angeles, LA, USA (former)


According to our database1, Xi Chen authored at least 104 papers between 2005 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Testing Sumsets is Hard.
CoRR, 2024

Testing Intersecting and Union-Closed Families.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023
Reducing Tarski to Unique Tarski (in the Black-box Model).
Electron. Colloquium Comput. Complex., 2023

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.
CoRR, 2023

Memory-Query Tradeoffs for Randomized Convex Optimization.
CoRR, 2023

Smoothed Complexity of SWAP in Local Graph Partitioning.
CoRR, 2023

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Streaming Euclidean MST to a Constant Factor.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximate Trace Reconstruction from a Single Trace.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Subset Sum in Time 2<sup>n/2</sup> / poly(n).
Proceedings of the Approximation, 2023

2022
A Lower Bound on Cycle-Finding in Sparse Digraphs.
ACM Trans. Algorithms, 2022

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.
SIAM J. Comput., 2022

SoK: Play-to-Earn Projects.
CoRR, 2022

On the complexity of dynamic submodular maximization.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

New streaming algorithms for high dimensional EMD and MST.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Average-Case Subset Balancing Problems.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Computational Hardness of the Hylland-Zeckhauser Scheme.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Upper Bounds for Finding Tarski Fixed Points.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Memory Bounds for Continual Learning.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Throttling Equilibria in Auction Markets.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Polynomial-time trace reconstruction in the smoothed complexity model.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Complexity of Pacing for Second-Price Auctions.
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Learning and testing junta distributions with sub cube conditioning.
Proceedings of the Conference on Learning Theory, 2021

2020
Learning and Testing Junta Distributions with Subcube Conditioning.
CoRR, 2020

Smoothed complexity of local max-cut and binary max-CSP.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Nearly optimal edge estimation with independent set queries.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Hedging in games: Faster convergence of external and swap regrets.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019
Distribution-free Junta Testing.
ACM Trans. Algorithms, 2019

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Electron. Colloquium Comput. Complex., 2019

A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.
Comput. Complex., 2019

Testing unateness nearly optimally.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.
Proceedings of the Approximation, 2019

An Axiomatic Approach to Block Rewards.
Proceedings of the 1st ACM Conference on Advances in Financial Technologies, 2019

2018
Settling the Query Complexity of Non-adaptive Junta Testing.
J. ACM, 2018

The complexity of optimal multidimensional pricing for a unit-demand buyer.
Games Econ. Behav., 2018

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
The Complexity of Non-Monotone Markets.
J. ACM, 2017

Complexity of Counting CSP with Complex Weights.
J. ACM, 2017

On the Complexity of Bundle-Pricing and Simple Mechanisms.
CoRR, 2017

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Boolean Unateness Testing with Õ(n<sup>3/4</sup>) Adaptive Queries.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
Proceedings of the Approximation, 2017

Sample-Based High-Dimensional Convexity Testing.
Proceedings of the Approximation, 2017

2016
Non-approximability of Bimatrix Nash Equilibria.
Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.
Encyclopedia of Algorithms, 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.
SIAM J. Comput., 2016

A Note on Teaching for VC Classes.
Electron. Colloquium Comput. Complex., 2016

Near-optimal small-depth lower bounds for small distance connectivity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Recursive Teaching Dimension of VC Classes.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

2015
Addition is exponentially harder than counting for shallow monotone circuits.
Electron. Colloquium Comput. Complex., 2015

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games.
CoRR, 2015

Boolean Function Monotonicity Testing Requires (Almost) n<sup>1/2</sup> Non-adaptive Queries.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Complexity of Nash Equilibria in Anonymous Games.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
The Complexity of Optimal Multidimensional Pricing.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Graph Homomorphisms with Complex Values: A Dichotomy Theorem.
SIAM J. Comput., 2013

How to Compress Interactive Communication.
SIAM J. Comput., 2013

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Faster Canonical Forms for Strongly Regular Graphs.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.
Proceedings of the Combinatorial Optimization and Applications, 2012

2011
Guest column: complexity dichotomies of counting problems.
SIGACT News, 2011

Partial Derivatives in Arithmetic Complexity and Beyond.
Found. Trends Theor. Comput. Sci., 2011

On Incentive Compatible Competitive Selection Protocols.
Algorithmica, 2011

A Complexity View of Markets with Social Influence.
Proceedings of the Innovations in Computer Science, 2011

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy
CoRR, 2010

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.
Comput. Complex., 2010

Quantum Separation of Local Search and Fixed Point Computation.
Algorithmica, 2010

On Tractable Exponential Sums.
Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

On the complexity of equilibria in markets with additively separable utilities.
Proceedings of the Behavioral and Quantitative Game Theory, 2010

2009
Market equilibria with hybrid linear-Leontief utilities.
Theor. Comput. Sci., 2009

On the complexity of 2D discrete fixed point problem.
Theor. Comput. Sci., 2009

Settling the complexity of computing two-player Nash equilibria.
J. ACM, 2009

Direct Sums in Randomized Communication Complexity.
Electron. Colloquium Comput. Complex., 2009

A Simplicial Approach for Discrete Fixed Point Theorems.
Algorithmica, 2009

Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
Non-approximability of Bimatrix Nash Equilibria.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Incentive Compatible Selection.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Complexity of Bimatrix Nash Equilibria.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Matching algorithmic bounds for finding a Brouwer fixed point.
J. ACM, 2008

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007
Complexity and approximation of the minimum recombinant haplotype configuration problem.
Theor. Comput. Sci., 2007

On searching a table consistent with division poset.
Theor. Comput. Sci., 2007

Recent development in computational complexity characterization of Nash equilibrium.
Comput. Sci. Rev., 2007

Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation
CoRR, 2007

The approximation complexity of win-lose games.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Computing Exact p-Value for Structured Motif.
Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006
Computing Nash Equilibria: Approximation and Smoothed Complexity.
Electron. Colloquium Comput. Complex., 2006

Sparse Games Are Hard.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Settling the Complexity of Two-Player Nash Equilibrium.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

On Incentive Compatible Competitive Selection Protocol.
Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set.
Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005
Settling the Complexity of 2-Player Nash-Equilibrium
Electron. Colloquium Comput. Complex., 2005

3-NASH is PPAD-Complete
Electron. Colloquium Comput. Complex., 2005

On algorithms for discrete and approximate brouwer fixed points.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005


  Loading...