×

zbMATH — the first resource for mathematics

Chen, Xi

Compute Distance To:
Author ID: chen.xi.1 Recent zbMATH articles by "Chen, Xi"
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

Publications by Year

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.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
77
2009
Complexity of counting CSP with complex weights. Zbl 1286.68182
Cai, Jin-Yi; Chen, Xi
18
2012
How to compress interactive communication. Zbl 1293.68116
Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup
16
2010
Graph homomorphisms with complex values: a dichotomy theorem. Zbl 1275.68073
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
15
2013
How to compress interactive communication. Zbl 1272.68138
Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup
14
2013
On the complexity of 2D discrete fixed point problem. Zbl 1223.68054
Chen, Xi; Deng, Xiaotie
12
2006
Partial derivatives in arithmetic complexity and beyond. Zbl 1278.68010
Chen, Xi; Kayal, Neeraj; Wigderson, Avi
11
2010
Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Zbl 1292.91113
Chen, Xi; Dai, Decheng; Du, Ye; Teng, Shang-Hua
9
2009
The approximation complexity of win-lose games. Zbl 1303.91009
Chen, Xi; Teng, Shang-Hua; Valiant, Paul
9
2007
On algorithms for discrete and approximate Brouwer fixed points (extended abstract). Zbl 1192.68351
Chen, Xi; Deng, Xiaotie
9
2005
Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094
Cai, 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.91293
Chen, Xi; Teng, Shang-Hua
7
2009
The complexity of non-monotone markets. Zbl 1293.91065
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
6
2013
On the complexity of 2D discrete fixed point problem. Zbl 1183.68294
Chen, Xi; Deng, Xiaotie
6
2009
Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. Zbl 1321.68300
Chen, Xi; De, Anindya; Servedio, Rocco A.; Tan, Li-Yang
5
2015
Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100
Cai, 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.68288
Cai, Jin-Yi; Chen, Xi; Li, Dong
5
2008
Complexity of counting CSP with complex weights. Zbl 1426.68114
Cai, Jin-Yi; Chen, Xi
4
2017
On the complexity of Nash equilibria in anonymous games. Zbl 1322.91005
Chen, Xi; Durfee, David; Orfanou, Anthi
4
2015
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David
4
2015
Quantile regression under memory constraint. Zbl 1436.62134
Chen, Xi; Liu, Weidong; Zhang, Yichen
3
2019
The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214
Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis
3
2018
Near-optimal small-depth lower bounds for small distance connectivity. Zbl 1373.68260
Chen, Xi; Oliveira, Igor C.; Servedio, Rocco A.; Tan, Li-Yang
3
2016
Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018
Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan
3
2012
Matching algorithmic bounds for finding a Brouwer fixed point. Zbl 1311.54038
Chen, Xi; Deng, Xiaotie
3
2008
A simplicial approach for discrete fixed point theorems. Zbl 1162.05365
Chen, Xi; Deng, Xiaotie
3
2006
Statistical inference for model parameters in stochastic gradient descent. Zbl 1440.62287
Chen, Xi; Lee, Jason D.; Tong, Xin T.; Zhang, Yichen
2
2020
Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492
Jiang, 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 07135856
She, Zhen-Su; Chen, Xi; Hussain, Fazle
2
2017
Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418
Cai, Jin-Yi; Chen, Xi
2
2017
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; Mcquillan, Colin; Richerby, David
2
2013
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
2010
On incentive compatible competitive selection protocol. Zbl 1162.05322
Chen, Xi; Deng, Xiaotie; Liu, Becky Jie
2
2006
Interface crack between dissimilar one-dimensional hexagonal quasicrystals with piezoelectric effect. Zbl 1428.74192
Hu, 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 07163396
Shui, Langquan; Liu, Yilun; Chen, Xi
1
2017
The complexity of non-monotone markets. Zbl 1427.91130
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
1
2017
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. Zbl 1370.68322
Chen, Xi; Waingarten, Erik; Xie, Jinyu
1
2017
Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems. Zbl 1293.05223
Chen, Xi; Sun, Xiaorui; Teng, Shang-Hua
1
2013
On incentive compatible competitive selection protocols. Zbl 1229.91072
Chen, Xi; Deng, Xiaotie; Liu, Becky Jie
1
2011
A simplicial approach for discrete fixed point theorems. Zbl 1176.58003
Chen, Xi; Deng, Xiaotie
1
2009
Market equilibria with hybrid linear-Leontief utilities. Zbl 1159.91425
Chen, Xi; Huang, Li-Sha; Teng, Shang-Hua
1
2009
Quantum separation of local search and fixed point computation. Zbl 1148.68382
Chen, Xi; Sun, Xiaoming; Teng, Shang-Hua
1
2008
Lattice embedding of direction-preserving correspondence over integrally convex set (extended abstract). Zbl 1137.91528
Chen, Xi; Deng, Xiaotie
1
2006
Complexity and approximation of the minimum recombination haplotype configuration problem. Zbl 1173.92312
Liu, Lan; Chen, Xi; Xiao, Jing; Jiang, Tao
1
2005
Statistical inference for model parameters in stochastic gradient descent. Zbl 1440.62287
Chen, Xi; Lee, Jason D.; Tong, Xin T.; Zhang, Yichen
2
2020
Structure evolution at early stage of boundary-layer transition: simulation and experiment. Zbl 07193492
Jiang, X. Y.; Lee, C. B.; Chen, X.; Smith, C. R.; Linden, P. F.
2
2020
Quantile regression under memory constraint. Zbl 1436.62134
Chen, Xi; Liu, Weidong; Zhang, Yichen
3
2019
Interface crack between dissimilar one-dimensional hexagonal quasicrystals with piezoelectric effect. Zbl 1428.74192
Hu, Keqiang; Jin, Hui; Yang, Zhenjun; Chen, Xi
1
2019
The complexity of optimal multidimensional pricing for a unit-demand buyer. Zbl 1400.91214
Chen, Xi; Diakonikolas, Ilias; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis
3
2018
Complexity of counting CSP with complex weights. Zbl 1426.68114
Cai, Jin-Yi; Chen, Xi
4
2017
Quantifying wall turbulence via a symmetry approach: a Lie group theory. Zbl 07135856
She, Zhen-Su; Chen, Xi; Hussain, Fazle
2
2017
Complexity dichotomies for counting problems. Volume 1. Boolean domain. Zbl 06821418
Cai, 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 07163396
Shui, Langquan; Liu, Yilun; Chen, Xi
1
2017
The complexity of non-monotone markets. Zbl 1427.91130
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
1
2017
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. Zbl 1370.68322
Chen, Xi; Waingarten, Erik; Xie, Jinyu
1
2017
Nonnegative weighted #CSP: an effective complexity dichotomy. Zbl 1356.68094
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
8
2016
Near-optimal small-depth lower bounds for small distance connectivity. Zbl 1373.68260
Chen, 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.68300
Chen, Xi; De, Anindya; Servedio, Rocco A.; Tan, Li-Yang
5
2015
On the complexity of Nash equilibria in anonymous games. Zbl 1322.91005
Chen, Xi; Durfee, David; Orfanou, Anthi
4
2015
The complexity of approximating conservative counting CSPs. Zbl 1354.68114
Chen, 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.68073
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan
15
2013
How to compress interactive communication. Zbl 1272.68138
Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup
14
2013
The complexity of non-monotone markets. Zbl 1293.91065
Chen, Xi; Paparas, Dimitris; Yannakakis, Mihalis
6
2013
The complexity of approximating conservative counting CSPs. Zbl 1354.68115
Chen, 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.05223
Chen, Xi; Sun, Xiaorui; Teng, Shang-Hua
1
2013
Complexity of counting CSP with complex weights. Zbl 1286.68182
Cai, Jin-Yi; Chen, Xi
18
2012
Inapproximability after uniqueness phase transition in two-spin systems. Zbl 1358.82018
Cai, Jin-Yi; Chen, Xi; Guo, Heng; Lu, Pinyan
3
2012
On incentive compatible competitive selection protocols. Zbl 1229.91072
Chen, Xi; Deng, Xiaotie; Liu, Becky Jie
1
2011
How to compress interactive communication. Zbl 1293.68116
Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup
16
2010
Partial derivatives in arithmetic complexity and beyond. Zbl 1278.68010
Chen, Xi; Kayal, Neeraj; Wigderson, Avi
11
2010
Quadratic lower bound for permanent vs. determinant in any characteristic. Zbl 1204.68100
Cai, Jin-Yi; Chen, Xi; Li, Dong
5
2010
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
2010
Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
77
2009
Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Zbl 1292.91113
Chen, 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.91293
Chen, Xi; Teng, Shang-Hua
7
2009
On the complexity of 2D discrete fixed point problem. Zbl 1183.68294
Chen, Xi; Deng, Xiaotie
6
2009
A simplicial approach for discrete fixed point theorems. Zbl 1176.58003
Chen, Xi; Deng, Xiaotie
1
2009
Market equilibria with hybrid linear-Leontief utilities. Zbl 1159.91425
Chen, 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.68288
Cai, Jin-Yi; Chen, Xi; Li, Dong
5
2008
Matching algorithmic bounds for finding a Brouwer fixed point. Zbl 1311.54038
Chen, Xi; Deng, Xiaotie
3
2008
Quantum separation of local search and fixed point computation. Zbl 1148.68382
Chen, Xi; Sun, Xiaoming; Teng, Shang-Hua
1
2008
The approximation complexity of win-lose games. Zbl 1303.91009
Chen, Xi; Teng, Shang-Hua; Valiant, Paul
9
2007
On the complexity of 2D discrete fixed point problem. Zbl 1223.68054
Chen, Xi; Deng, Xiaotie
12
2006
A simplicial approach for discrete fixed point theorems. Zbl 1162.05365
Chen, Xi; Deng, Xiaotie
3
2006
On incentive compatible competitive selection protocol. Zbl 1162.05322
Chen, Xi; Deng, Xiaotie; Liu, Becky Jie
2
2006
Lattice embedding of direction-preserving correspondence over integrally convex set (extended abstract). Zbl 1137.91528
Chen, Xi; Deng, Xiaotie
1
2006
On algorithms for discrete and approximate Brouwer fixed points (extended abstract). Zbl 1192.68351
Chen, Xi; Deng, Xiaotie
9
2005
Complexity and approximation of the minimum recombination haplotype configuration problem. Zbl 1173.92312
Liu, Lan; Chen, Xi; Xiao, Jing; Jiang, Tao
1
2005
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

Citations by Year