Follow
Xi Chen
Xi Chen
Verified email at cs.columbia.edu - Homepage
Title
Cited by
Cited by
Year
Settling the complexity of computing two-player Nash equilibria
X Chen, X Deng, SH Teng
Journal of the ACM (JACM) 56 (3), 14, 2009
843*2009
Settling the complexity of two-player Nash equilibrium
X Chen, X Deng
Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium …, 2006
7572006
How to compress interactive communication
B Barak, M Braverman, X Chen, A Rao
SIAM Journal on Computing, 2013
2652013
3-Nash is PPAD-complete
X Chen, X Deng
Electronic Colloquium on Computational Complexity 134, 2-29, 2005
1592005
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
1392009
Graph homomorphisms with complex values: A dichotomy theorem
JY Cai, X Chen, P Lu
SIAM Journal on Computing 42 (3), 924-1029, 2013
1362013
Complexity of counting CSP with complex weights
JY Cai, X Chen
Journal of the ACM (JACM) 64 (3), 1-39, 2017
1102017
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
1052011
The complexity of non-monotone markets
X Chen, D Paparas, M Yannakakis
Journal of the ACM (JACM) 64 (3), 1-56, 2017
104*2017
On the complexity of 2D discrete fixed point problem
X Chen, X Deng
Theoretical Computer Science 410 (44), 4448-4456, 2009
1002009
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
852014
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
752009
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
702015
Nonnegative weighted# CSP: an effective complexity dichotomy
JY Cai, X Chen, P Lu
SIAM Journal on Computing 45 (6), 2177-2198, 2016
692016
An axiomatic approach to block rewards
X Chen, C Papadimitriou, T Roughgarden
Proceedings of the 1st ACM Conference on Advances in Financial Technologies …, 2019
662019
Matching algorithmic bounds for finding a Brouwer fixed point
X Chen, X Deng
Journal of the ACM (JACM) 55 (3), 1-26, 2008
65*2008
Hedging in games: Faster convergence of external and swap regrets
X Chen, B Peng
Advances in Neural Information Processing Systems 33, 18990-18999, 2020
542020
Sparse games are hard
X Chen, X Deng, SH Teng
Internet and Network Economics: Second International Workshop, WINE 2006 …, 2006
542006
Complexity dichotomies for counting problems: Volume 1, Boolean domain
JY Cai, X Chen
Cambridge University Press, 2017
532017
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
472014
The system can't perform the operation now. Try again later.
Articles 1–20