Edit Profile Chen, Xi Compute Distance To: Compute Author ID: chen.xi.1 Published as: Chen, X.; Chen, Xi Homepage: http://www.cs.columbia.edu/~xichen External Links: ORCID · dblp Documents Indexed: 98 Publications since 2005, including 3 Books all top 5 Co-Authors 0 single-authored 11 Deng, Xiao-Tie 10 Cai, Jin-Yi 8 Servedio, Rocco A. 8 Teng, Shang-Hua 6 Lu, Pinyan 6 Xie, Jinyu 6 Yannakakis, Mihalis 5 Paparas, Dimitris 5 Waingarten, Erik 4 Tan, Liyang 3 Sun, Xiaorui 2 Barak, Boaz 2 Braverman, Mark 2 Diakonikolas, Ilias 2 Dyer, Martin E. 2 Goldberg, Leslie Ann 2 Jerrum, Mark R. 2 Li, Dong 2 Liu, Becky Jie 2 Liu, Zhengyang 2 Mcquillan, Colin 2 Oliveira, Igor Carboni 2 Rao, Anup 2 Richerby, David M. 2 Sheng, Ying 2 Sun, Xiaoming 1 Cheng, Yongxi 1 Cheng, Yu 1 Dai, Decheng 1 De, Anindya K. 1 Du, Ye 1 Durfee, David 1 Guo, Chenghao 1 Guo, Heng 1 Huang, Li-Sha 1 Jiang, Tao 1 Kayal, Neeraj 1 Levi, Amit 1 Li, Ming 1 Lipton, Richard J. 1 Liu, Lan 1 Matikas, George 1 Orfanou, Anthi 1 Randolph, Timothy W. 1 Sun, Timothy 1 Tang, Bo 1 Valiant, Paul 1 Vlatakis-Gkaragkounis, Emmanouil V. 1 Wigderson, Avi 1 Xiao, Jing 1 Yin, Yiqun Lisa 1 Zhang, Jing 1 Zhang, Xinzhi all top 5 Serials 5 Journal of the ACM 3 SIAM Journal on Computing 3 Theoretical Computer Science 3 Algorithmica 2 Computational Complexity 1 Journal of Computer and System Sciences 1 Games and Economic Behavior 1 Foundations and Trends in Theoretical Computer Science 1 ACM Transactions on Algorithms 1 Computer Science Review all top 5 Fields 47 Computer science (68-XX) 17 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 8 Combinatorics (05-XX) 2 Biology and other natural sciences (92-XX) 1 Mathematical logic and foundations (03-XX) 1 Field theory and polynomials (12-XX) 1 Commutative algebra (13-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Quantum theory (81-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH 44 Publications have been cited 287 times in 222 Documents Cited by ▼ Year ▼ Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua 77 2009 Complexity of counting CSP with complex weights. Zbl 1286.68182Cai, Jin-Yi; Chen, Xi 18 2012 How to compress interactive communication. Zbl 1293.68116Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup 16 2010 Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 15 2013 How to compress interactive communication. Zbl 1272.68138Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup 14 2013 On the complexity of 2D discrete fixed point problem. Zbl 1223.68054Chen, Xi; Deng, Xiaotie 12 2006 Partial derivatives in arithmetic complexity and beyond. Zbl 1278.68010Chen, Xi; Kayal, Neeraj; Wigderson, Avi 11 2010 Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Zbl 1292.91113Chen, Xi; Dai, Decheng; Du, Ye; Teng, Shang-Hua 9 2009 The approximation complexity of win-lose games. Zbl 1303.91009Chen, Xi; Teng, Shang-Hua; Valiant, Paul 9 2007 On algorithms for discrete and approximate Brouwer fixed points (extended abstract). Zbl 1192.68351Chen, Xi; Deng, Xiaotie 9 2005 Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 8 2016 Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria. Zbl 1273.91293Chen, Xi; Teng, Shang-Hua 7 2009 The complexity of non-monotone markets. Zbl 1293.91065Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 6 2013 On the complexity of 2D discrete fixed point problem. Zbl 1183.68294Chen, Xi; Deng, Xiaotie 6 2009 Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. Zbl 1321.68300Chen, Xi; De, Anindya; Servedio, Rocco A.; Tan, Li-Yang 5 2015 Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100Cai, Jin-Yi; Chen, Xi; Li, Dong 5 2010 A quadratic lower bound for the permanent and determinant problem over any characteristic \(\neq 2\). Zbl 1231.68288Cai, Jin-Yi; Chen, Xi; Li, Dong 5 2008 Complexity of counting CSP with complex weights. Zbl 1426.68114Cai, Jin-Yi; Chen, Xi 4 2017 On the complexity of Nash equilibria in anonymous games. Zbl 1322.91005Chen, Xi; Durfee, David; Orfanou, Anthi 4 2015 The complexity of approximating conservative counting CSPs. Zbl 1354.68114Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David 4 2015 Quantile regression under memory constraint. Zbl 1436.62134Chen, Xi; Liu, Weidong; Zhang, Yichen 3 2019 The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis 3 2018 Near-optimal small-depth lower bounds for small distance connectivity. Zbl 1373.68260Chen, Xi; Oliveira, Igor C.; Servedio, Rocco A.; Tan, Li-Yang 3 2016 Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan 3 2012 Matching algorithmic bounds for finding a Brouwer fixed point. Zbl 1311.54038Chen, Xi; Deng, Xiaotie 3 2008 A simplicial approach for discrete fixed point theorems. Zbl 1162.05365Chen, Xi; Deng, Xiaotie 3 2006 Statistical inference for model parameters in stochastic gradient descent. Zbl 1440.62287Chen, Xi; Lee, Jason D.; Tong, Xin T.; Zhang, Yichen 2 2020 Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492Jiang, X. Y.; Lee, C. B.; Chen, X.; Smith, C. R.; Linden, P. F. 2 2020 Quantifying wall turbulence via a symmetry approach: a Lie group theory. Zbl 07135856She, Zhen-Su; Chen, Xi; Hussain, Fazle 2 2017 Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418Cai, Jin-Yi; Chen, Xi 2 2017 The complexity of approximating conservative counting CSPs. Zbl 1354.68115Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David 2 2013 On tractable exponential sums. Zbl 1288.68104Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan 2 2010 On incentive compatible competitive selection protocol. Zbl 1162.05322Chen, Xi; Deng, Xiaotie; Liu, Becky Jie 2 2006 Interface crack between dissimilar one-dimensional hexagonal quasicrystals with piezoelectric effect. Zbl 1428.74192Hu, Keqiang; Jin, Hui; Yang, Zhenjun; Chen, Xi 1 2019 Three dimensional wave propagation in time-varying materials: a mathematical model based on the weak solutions of continuity in the moving property interface. Zbl 07163396Shui, Langquan; Liu, Yilun; Chen, Xi 1 2017 The complexity of non-monotone markets. Zbl 1427.91130Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 1 2017 Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. Zbl 1370.68322Chen, Xi; Waingarten, Erik; Xie, Jinyu 1 2017 Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems. Zbl 1293.05223Chen, Xi; Sun, Xiaorui; Teng, Shang-Hua 1 2013 On incentive compatible competitive selection protocols. Zbl 1229.91072Chen, Xi; Deng, Xiaotie; Liu, Becky Jie 1 2011 A simplicial approach for discrete fixed point theorems. Zbl 1176.58003Chen, Xi; Deng, Xiaotie 1 2009 Market equilibria with hybrid linear-Leontief utilities. Zbl 1159.91425Chen, Xi; Huang, Li-Sha; Teng, Shang-Hua 1 2009 Quantum separation of local search and fixed point computation. Zbl 1148.68382Chen, Xi; Sun, Xiaoming; Teng, Shang-Hua 1 2008 Lattice embedding of direction-preserving correspondence over integrally convex set (extended abstract). Zbl 1137.91528Chen, Xi; Deng, Xiaotie 1 2006 Complexity and approximation of the minimum recombination haplotype configuration problem. Zbl 1173.92312Liu, Lan; Chen, Xi; Xiao, Jing; Jiang, Tao 1 2005 Statistical inference for model parameters in stochastic gradient descent. Zbl 1440.62287Chen, Xi; Lee, Jason D.; Tong, Xin T.; Zhang, Yichen 2 2020 Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492Jiang, X. Y.; Lee, C. B.; Chen, X.; Smith, C. R.; Linden, P. F. 2 2020 Quantile regression under memory constraint. Zbl 1436.62134Chen, Xi; Liu, Weidong; Zhang, Yichen 3 2019 Interface crack between dissimilar one-dimensional hexagonal quasicrystals with piezoelectric effect. Zbl 1428.74192Hu, Keqiang; Jin, Hui; Yang, Zhenjun; Chen, Xi 1 2019 The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis 3 2018 Complexity of counting CSP with complex weights. Zbl 1426.68114Cai, Jin-Yi; Chen, Xi 4 2017 Quantifying wall turbulence via a symmetry approach: a Lie group theory. Zbl 07135856She, Zhen-Su; Chen, Xi; Hussain, Fazle 2 2017 Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418Cai, Jin-Yi; Chen, Xi 2 2017 Three dimensional wave propagation in time-varying materials: a mathematical model based on the weak solutions of continuity in the moving property interface. Zbl 07163396Shui, Langquan; Liu, Yilun; Chen, Xi 1 2017 The complexity of non-monotone markets. Zbl 1427.91130Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 1 2017 Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. Zbl 1370.68322Chen, Xi; Waingarten, Erik; Xie, Jinyu 1 2017 Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 8 2016 Near-optimal small-depth lower bounds for small distance connectivity. Zbl 1373.68260Chen, Xi; Oliveira, Igor C.; Servedio, Rocco A.; Tan, Li-Yang 3 2016 Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. Zbl 1321.68300Chen, Xi; De, Anindya; Servedio, Rocco A.; Tan, Li-Yang 5 2015 On the complexity of Nash equilibria in anonymous games. Zbl 1322.91005Chen, Xi; Durfee, David; Orfanou, Anthi 4 2015 The complexity of approximating conservative counting CSPs. Zbl 1354.68114Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David 4 2015 Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073Cai, Jin-Yi; Chen, Xi; Lu, Pinyan 15 2013 How to compress interactive communication. Zbl 1272.68138Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup 14 2013 The complexity of non-monotone markets. Zbl 1293.91065Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis 6 2013 The complexity of approximating conservative counting CSPs. Zbl 1354.68115Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David 2 2013 Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems. Zbl 1293.05223Chen, Xi; Sun, Xiaorui; Teng, Shang-Hua 1 2013 Complexity of counting CSP with complex weights. Zbl 1286.68182Cai, Jin-Yi; Chen, Xi 18 2012 Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan 3 2012 On incentive compatible competitive selection protocols. Zbl 1229.91072Chen, Xi; Deng, Xiaotie; Liu, Becky Jie 1 2011 How to compress interactive communication. Zbl 1293.68116Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup 16 2010 Partial derivatives in arithmetic complexity and beyond. Zbl 1278.68010Chen, Xi; Kayal, Neeraj; Wigderson, Avi 11 2010 Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100Cai, Jin-Yi; Chen, Xi; Li, Dong 5 2010 On tractable exponential sums. Zbl 1288.68104Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan 2 2010 Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua 77 2009 Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Zbl 1292.91113Chen, Xi; Dai, Decheng; Du, Ye; Teng, Shang-Hua 9 2009 Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria. Zbl 1273.91293Chen, Xi; Teng, Shang-Hua 7 2009 On the complexity of 2D discrete fixed point problem. Zbl 1183.68294Chen, Xi; Deng, Xiaotie 6 2009 A simplicial approach for discrete fixed point theorems. Zbl 1176.58003Chen, Xi; Deng, Xiaotie 1 2009 Market equilibria with hybrid linear-Leontief utilities. Zbl 1159.91425Chen, Xi; Huang, Li-Sha; Teng, Shang-Hua 1 2009 A quadratic lower bound for the permanent and determinant problem over any characteristic \(\neq 2\). Zbl 1231.68288Cai, Jin-Yi; Chen, Xi; Li, Dong 5 2008 Matching algorithmic bounds for finding a Brouwer fixed point. Zbl 1311.54038Chen, Xi; Deng, Xiaotie 3 2008 Quantum separation of local search and fixed point computation. Zbl 1148.68382Chen, Xi; Sun, Xiaoming; Teng, Shang-Hua 1 2008 The approximation complexity of win-lose games. Zbl 1303.91009Chen, Xi; Teng, Shang-Hua; Valiant, Paul 9 2007 On the complexity of 2D discrete fixed point problem. Zbl 1223.68054Chen, Xi; Deng, Xiaotie 12 2006 A simplicial approach for discrete fixed point theorems. Zbl 1162.05365Chen, Xi; Deng, Xiaotie 3 2006 On incentive compatible competitive selection protocol. Zbl 1162.05322Chen, Xi; Deng, Xiaotie; Liu, Becky Jie 2 2006 Lattice embedding of direction-preserving correspondence over integrally convex set (extended abstract). Zbl 1137.91528Chen, Xi; Deng, Xiaotie 1 2006 On algorithms for discrete and approximate Brouwer fixed points (extended abstract). Zbl 1192.68351Chen, Xi; Deng, Xiaotie 9 2005 Complexity and approximation of the minimum recombination haplotype configuration problem. Zbl 1173.92312Liu, Lan; Chen, Xi; Xiao, Jing; Jiang, Tao 1 2005 all cited Publications top 5 cited Publications all top 5 Cited by 386 Authors 11 Cai, Jin-Yi 10 Chen, Xi 9 Goldberg, Paul W. 8 Fearnley, John 7 Braverman, Mark 7 Vazirani, Vijay V. 6 Deligkas, Argyrios 6 Goldberg, Leslie Ann 6 Lu, Pinyan 6 Mehta, Ruta 6 Meir, Or 6 Savani, Rahul 5 Guo, Heng 4 Chattopadhyay, Arkadev 4 Deng, Xiao-Tie 4 Garg, Jugal 4 Jain, Rahul 4 Jerrum, Mark R. 4 Mavronicolas, Marios 4 Meunier, Frédéric 4 Papadimitriou, Christos Harilaos 4 Spirakis, Paul G. 4 Williams, Tyson 3 Auletta, Vincenzo 3 Bilò, Vittorio 3 Conitzer, Vincent 3 Ferraioli, Diodato 3 Galanis, Andreas 3 Ikenmeyer, Christian 3 Koucký, Michal 3 Makino, Kazuhisa 3 Monien, Burkhard 3 Pasquale, Francesco 3 Persiano, Giuseppe 3 Pitassi, Toniann 3 Qi, Qi 3 Segev, Gil 3 Štefankovič, Daniel 3 Turner, Jacob M. 3 Vigoda, Eric 3 Weinstein, Omri 3 Zhang, Qin 2 Barman, Siddharth 2 Barvinok, Alexander I. 2 Boonyasiriwat, Ch. 2 Brody, Joshua E. 2 Bu, Tianming 2 Bulatov, Andrei A. 2 Bürgisser, Peter 2 Curticapean, Radu 2 Czumaj, Artur 2 Dang, Chuangyin 2 Daskalakis, Constantinos 2 Fasoulakis, Michail 2 Fontes, Lila 2 Fu, Zhiguo 2 Garg, Ankit 2 Grauberger, W. 2 Grigorescu, Elena 2 Hermelin, Danny 2 Huang, Chien-Chung 2 Hubáček, Pavel 2 Jansen, Maurice J. 2 Jurdziński, Marcin 2 Kakimura, Naonori 2 Kerenidis, Iordanis 2 Kimms, Alf 2 Komargodski, Ilan 2 Kratsch, Stefan 2 Kumar, Akash 2 Landsberg, Joseph Montague 2 Laplante, Sophie 2 Lee, Chang-Boon 2 Linden, Paul F. 2 Loff, Bruno 2 Mcquillan, Colin 2 Moran, Shay 2 Murota, Kazuo 2 Panova, Greta 2 Phillips, Jeff M. 2 Richerby, David M. 2 Roland, Jérémie 2 Rossman, Benjamin 2 Saha, Chandan 2 Santha, Miklos 2 Sikorski, Krzysztof A. 2 Smith, C. Ray 2 Soberón, Pablo 2 Sørensen, Troels Bjerre 2 Sumita, Hanna 2 Sun, Xiaoming 2 Tang, Bo 2 Teng, Shang-Hua 2 Turchetta, Stefano 2 Verbin, Elad 2 Wahlström, Magnus 2 Wigderson, Avi 2 Wimmer, Karl 2 Wojtczak, Dominik 2 Xia, Mingji ...and 286 more Authors all top 5 Cited in 63 Serials 24 SIAM Journal on Computing 22 Algorithmica 13 Journal of Computer and System Sciences 11 Theoretical Computer Science 9 Computational Complexity 8 Information and Computation 8 Theory of Computing Systems 5 Games and Economic Behavior 4 Journal of Fluid Mechanics 3 Discrete Applied Mathematics 3 Mathematics of Operations Research 3 Journal of Machine Learning Research (JMLR) 2 Discrete Mathematics 2 Information Processing Letters 2 Israel Journal of Mathematics 2 Advances in Mathematics 2 International Journal of Game Theory 2 Journal of Algebra 2 Journal of Complexity 2 Journal of the American Mathematical Society 2 SIAM Journal on Discrete Mathematics 2 Journal of Cryptology 2 Distributed Computing 2 Foundations of Computational Mathematics 2 Computer Science Review 1 Acta Mechanica 1 Artificial Intelligence 1 Communications in Algebra 1 Communications in Mathematical Physics 1 Moscow University Mathematics Bulletin 1 Mathematics of Computation 1 The Annals of Statistics 1 Journal of Combinatorial Theory. Series A 1 Journal of Multivariate Analysis 1 Synthese 1 Advances in Applied Mathematics 1 Combinatorica 1 Journal of Symbolic Computation 1 Computers & Operations Research 1 Annals of Operations Research 1 Differential Geometry and its Applications 1 Applied Mathematical Modelling 1 European Journal of Operational Research 1 Linear Algebra and its Applications 1 Proceedings of the National Academy of Sciences of the United States of America 1 SIAM Review 1 Bulletin of the American Mathematical Society. New Series 1 Mathematical Programming. Series A. Series B 1 Computational Optimization and Applications 1 Economic Theory 1 Journal of Inequalities and Applications 1 Journal of Combinatorial Optimization 1 Journal of the ACM 1 International Game Theory Review 1 OR Spectrum 1 Analysis and Applications (Singapore) 1 Parallel Processing Letters 1 Annali dell’Università di Ferrara. Sezione VII. Scienze Matematiche 1 Electronic Journal of Statistics 1 Japanese Journal of Mathematics. 3rd Series 1 Games 1 ACM Transactions on Computation Theory 1 Research in the Mathematical Sciences all top 5 Cited in 32 Fields 158 Computer science (68-XX) 80 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 25 Combinatorics (05-XX) 23 Operations research, mathematical programming (90-XX) 18 Information and communication theory, circuits (94-XX) 9 Probability theory and stochastic processes (60-XX) 7 Statistical mechanics, structure of matter (82-XX) 5 Linear and multilinear algebra; matrix theory (15-XX) 5 Group theory and generalizations (20-XX) 5 Convex and discrete geometry (52-XX) 5 Quantum theory (81-XX) 4 Field theory and polynomials (12-XX) 4 Algebraic geometry (14-XX) 4 Statistics (62-XX) 4 Numerical analysis (65-XX) 4 Fluid mechanics (76-XX) 3 Mathematical logic and foundations (03-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Commutative algebra (13-XX) 2 History and biography (01-XX) 2 Category theory; homological algebra (18-XX) 2 Mechanics of deformable solids (74-XX) 1 General algebraic systems (08-XX) 1 Number theory (11-XX) 1 Topological groups, Lie groups (22-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Operator theory (47-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year