Xi Chen
According to our database^{1},
Xi Chen
authored at least 77 papers
between 2005 and 2020.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org
On csauthors.net:
Bibliography
2020
Nearly optimal edge estimation with independent set queries.
Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, 2020
2019
Distributionfree Junta Testing.
ACM Trans. Algorithms, 2019
Random Restrictions of HighDimensional Distributions and Uniformity Testing with Subcube Conditioning.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Smoothed complexity of local MaxCut and binary MaxCSP.
CoRR, 2019
A Lower Bound on CycleFinding in Sparse Digraphs.
CoRR, 2019
A decidable dichotomy theorem on directed graph homomorphisms with nonnegative 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 AverageCase Population Recovery in the Presence of Insertions and Deletions.
Proceedings of the Approximation, 2019
2018
Settling the Query Complexity of Nonadaptive Junta Testing.
J. ACM, 2018
The complexity of optimal multidimensional pricing for a unitdemand buyer.
Games and Economic Behavior, 2018
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
2017
The Complexity of NonMonotone Markets.
J. ACM, 2017
Complexity of Counting CSP with Complex Weights.
J. ACM, 2017
On the Complexity of BundlePricing 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
WellSupported 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^{3/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
SampleBased HighDimensional Convexity Testing.
Proceedings of the Approximation, 2017
2016
Nonapproximability 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
Nearoptimal smalldepth lower bounds for small distance connectivity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Tight Bounds for the DistributionFree Testing of Monotone Conjunctions.
Proceedings of the TwentySeventh Annual ACMSIAM 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
WellSupported versus Approximate Nash Equilibria: Query Complexity of Large Games.
CoRR, 2015
Boolean Function Monotonicity Testing Requires (Almost) n^{1/2} Nonadaptive Queries.
Proceedings of the FortySeventh Annual ACM on Symposium on Theory of Computing, 2015
On the Complexity of Nash Equilibria in Anonymous Games.
Proceedings of the FortySeventh 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 TwentyFifth Annual ACMSIAM 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
Multistage design for quasipolynomialtime isomorphism testing of steiner 2systems.
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 TwoSpin 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
Nonnegatively Weighted #CSP: An Effective Complexity Dichotomy.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
2010
Nonnegative 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 linearLeontief utilities.
Theor. Comput. Sci., 2009
On the complexity of 2D discrete fixed point problem.
Theor. Comput. Sci., 2009
Settling the complexity of computing twoplayer 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 ArrowDebreu Equilibria.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009
Settling the Complexity of ArrowDebreu Equilibria in Markets with Additively Separable Utilities.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2008
Nonapproximability 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 FixedPoint Computation
CoRR, 2007
The approximation complexity of winlose games.
Proceedings of the Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2007
Paths Beyond Local Search: A Tight Bound for Randomized FixedPoint Computation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007
Computing Exact pValue 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 TwoPlayer 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 DirectionPreserving Correspondence over Integrally Convex Set.
Proceedings of the Algorithmic Aspects in Information and Management, 2006
2005
Settling the Complexity of 2Player NashEquilibrium
Electronic Colloquium on Computational Complexity (ECCC), 2005
3NASH is PPADComplete
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