Xi Chen
Xi Chen
Verified email at cs.columbia.edu - Homepage
Cited by
Cited by
Settling the complexity of two-player Nash equilibrium
X Chen, X Deng
Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium …, 2006
Settling the complexity of computing two-player Nash equilibria
X Chen, X Deng, SH Teng
Journal of the ACM (JACM) 56 (3), 14, 2009
How to compress interactive communication
B Barak, M Braverman, X Chen, A Rao
SIAM Journal on Computing, 2013
3-Nash is PPAD-complete
X Chen, X Deng
Electronic Colloquium on Computational Complexity 134, 2-29, 2005
Graph homomorphisms with complex values: A dichotomy theorem
JY Cai, X Chen, P Lu
SIAM Journal on Computing 42 (3), 924-1029, 2013
Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities
X Chen, D Dai, Y Du, SH Teng
50th Annual IEEE Symposium on Foundations of Computer Science, 2009
Complexity of counting CSP with complex weights
JY Cai, X Chen
Journal of the ACM (JACM) 64 (3), 1-39, 2017
Partial Derivatives in Arithmetic Complexity and Beyond
X Chen, N Kayal, A Wigderson
Foundations and Trends® in Theoretical Computer Science 6 (1-2), 1-138, 2011
On the complexity of 2D discrete fixed point problem
X Chen, X Deng
Theoretical Computer Science 410 (44), 4448-4456, 2009
New algorithms and lower bounds for monotonicity testing
X Chen, RA Servedio, LY Tan
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 286-295, 2014
Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria
X Chen, SH Teng
International Symposium on Algorithms and Computation, 647-656, 2009
The complexity of non-monotone markets
X Chen, D Paparas, M Yannakakis
Journal of the ACM (JACM) 64 (3), 1-56, 2017
Boolean function monotonicity testing requires (almost) n 1/2 non-adaptive queries
X Chen, A De, RA Servedio, LY Tan
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
Nonnegative weighted# CSP: An effective complexity dichotomy
JY Cai, X Chen, P Lu
SIAM Journal on Computing 45 (6), 2177-2198, 2016
Matching algorithmic bounds for finding a Brouwer fixed point
X Chen, X Deng
Journal of the ACM (JACM) 55 (3), 1-26, 2008
Sparse games are hard
X Chen, X Deng, SH Teng
International Workshop on Internet and Network Economics, 262-273, 2006
The complexity of optimal multidimensional pricing
X Chen, I Diakonikolas, D Paparas, X Sun, M Yannakakis
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete …, 2014
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
JY Cai, X Chen
2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 437-446, 2010
The approximation complexity of win-lose games
X Chen, SH Teng, P Valiant
Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms …, 2007
The complexity of approximating conservative counting CSPs
X Chen, M Dyer, LA Goldberg, M Jerrum, P Lu, C McQuillan, D Richerby
Journal of Computer and System Sciences 81 (1), 311-329, 2015
The system can't perform the operation now. Try again later.
Articles 1–20