Xi Chen

According to our database1, Xi Chen authored at least 77 papers between 2005 and 2020.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

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

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Smoothed complexity of local Max-Cut and binary Max-CSP.
CoRR, 2019

A Lower Bound on Cycle-Finding in Sparse Digraphs.
CoRR, 2019

A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.
Computational Complexity, 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

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 and Economic Behavior, 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 Õ(n3/4) 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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 2015

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

Boolean Function Monotonicity Testing Requires (Almost) n1/2 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.
Foundations and Trends in Theoretical Computer Science, 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.
Computational Complexity, 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.
Electronic Colloquium on Computational Complexity (ECCC), 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.
Computer Science Review, 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.
Electronic Colloquium on Computational Complexity (ECCC), 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
Electronic Colloquium on Computational Complexity (ECCC), 2005

3-NASH is PPAD-Complete
Electronic Colloquium on Computational Complexity (ECCC), 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...