Остановите войну!
for scientists:
default search action
Xi Chen 0001
- > Home > Persons > Xi Chen 0001
Publications
- 2024
- [c76]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Testing Intersecting and Union-Closed Families. ITCS 2024: 33:1-33:23 - [c75]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA 2024: 4321-4337 - [c73]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis:
Smoothed Complexity of SWAP in Local Graph Partitioning. SODA 2024: 5057-5083 - [i71]Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir:
Testing Sumsets is Hard. CoRR abs/2401.07242 (2024) - [i70]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. Electron. Colloquium Comput. Complex. TR24: TR24-057 (2024) - 2023
- [c72]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Subset Sum in Time 2n/2 / poly(n). APPROX/RANDOM 2023: 39:1-39:18 - [c71]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (In the Black-Box Model). CCC 2023: 21:1-21:23 - [c70]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Approximate Trace Reconstruction from a Single Trace. SODA 2023: 605-637 - [c69]Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Streaming Euclidean MST to a Constant Factor. STOC 2023: 156-169 - [c68]Xi Chen, Binghui Peng:
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules. STOC 2023: 698-709 - [i69]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Subset Sum in Time 2n/2/poly(n). CoRR abs/2301.07134 (2023) - [i68]Xi Chen, Binghui Peng:
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules. CoRR abs/2303.16388 (2023) - [i67]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis:
Smoothed Complexity of SWAP in Local Graph Partitioning. CoRR abs/2305.15804 (2023) - [i66]Xi Chen, Binghui Peng:
Memory-Query Tradeoffs for Randomized Convex Optimization. CoRR abs/2306.12534 (2023) - [i65]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR abs/2309.12513 (2023) - [i64]Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Testing Intersecting and Union-Closed Families. CoRR abs/2311.11119 (2023) - [i63]Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (in the Black-box Model). Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j24]Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer. SIAM J. Comput. 51(3): 492-548 (2022) - [j23]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms 18(4): 31:1-31:23 (2022) - [c67]Xi Chen, Christos H. Papadimitriou, Binghui Peng:
Memory Bounds for Continual Learning. FOCS 2022: 519-530 - [c66]Xi Chen, Yuhao Li:
Improved Upper Bounds for Finding Tarski Fixed Points. EC 2022: 1108-1118 - [c65]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Average-Case Subset Balancing Problems. SODA 2022: 743-778 - [c64]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. SODA 2022: 779-821 - [c63]Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis:
Computational Hardness of the Hylland-Zeckhauser Scheme. SODA 2022: 2253-2268 - [c62]Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
New streaming algorithms for high dimensional EMD and MST. STOC 2022: 222-233 - [c61]Xi Chen, Binghui Peng:
On the complexity of dynamic submodular maximization. STOC 2022: 1685-1698 - [i62]Xi Chen, Yuhao Li:
Improved Upper Bounds for Finding Tarski Fixed Points. CoRR abs/2202.05913 (2022) - [i61]Xi Chen, Christos H. Papadimitriou, Binghui Peng:
Memory Bounds for Continual Learning. CoRR abs/2204.10830 (2022) - [i60]Jingfan Yu, Mengqian Zhang, Xi Chen, Zhixuan Fang:
SoK: Play-to-Earn Projects. CoRR abs/2211.01000 (2022) - [i59]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Approximate Trace Reconstruction from a Single Trace. CoRR abs/2211.03292 (2022) - [i58]Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Streaming Euclidean MST to a Constant Factor. CoRR abs/2212.06546 (2022) - 2021
- [c60]Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Learning and testing junta distributions with sub cube conditioning. COLT 2021: 1060-1113 - [c59]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. ITCS 2021: 20:1-20:20 - [c57]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the smoothed complexity model. SODA 2021: 54-73 - [c56]Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten:
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. SODA 2021: 321-336 - [i56]Thomas Chen, Xi Chen, Binghui Peng, Mihalis Yannakakis:
Computational Hardness of the Hylland-Zeckhauser Scheme. CoRR abs/2107.05746 (2021) - [i54]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. CoRR abs/2107.11530 (2021) - [i53]Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio:
Average-Case Subset Balancing Problems. CoRR abs/2110.14607 (2021) - [i52]Xi Chen, Binghui Peng:
On the Complexity of Dynamic Submodular Maximization. CoRR abs/2111.03198 (2021) - [i51]Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
New Streaming Algorithms for High Dimensional EMD and MST. CoRR abs/2111.03528 (2021) - 2020
- [c54]Xi Chen, Binghui Peng:
Hedging in games: Faster convergence of external and swap regrets. NeurIPS 2020 - [c53]Xi Chen, Amit Levi, Erik Waingarten:
Nearly optimal edge estimation with independent set queries. SODA 2020: 2916-2935 - [c52]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. SODA 2020: 2936-2952 - [c51]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang:
Smoothed complexity of local max-cut and binary max-CSP. STOC 2020: 1052-1065 - [i50]Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten:
Learning and Testing Junta Distributions with Subcube Conditioning. CoRR abs/2004.12496 (2020) - [i49]Xi Chen, Binghui Peng:
Hedging in games: Faster convergence of external and swap regrets. CoRR abs/2006.04953 (2020) - [i48]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the smoothed complexity model. CoRR abs/2008.12386 (2020) - [i47]Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha:
Polynomial-time trace reconstruction in the low deletion rate regime. CoRR abs/2012.02844 (2020) - 2019
- [j22]Jin-Yi Cai, Xi Chen:
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Comput. Complex. 28(3): 345-408 (2019) - [j21]Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free Junta Testing. ACM Trans. Algorithms 15(1): 1:1-1:23 (2019) - [c50]Xi Chen, Christos H. Papadimitriou, Tim Roughgarden:
An Axiomatic Approach to Block Rewards. AFT 2019: 124-131 - [c49]Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha:
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. APPROX-RANDOM 2019: 44:1-44:18 - [c48]Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha:
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. FOCS 2019: 745-768 - [c47]Xi Chen, Erik Waingarten:
Testing unateness nearly optimally. STOC 2019: 547-558 - [i46]Xi Chen, Erik Waingarten:
Testing Unateness Nearly Optimally. CoRR abs/1904.05309 (2019) - [i45]Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha:
Beyond trace reconstruction: Population recovery from the deletion channel. CoRR abs/1904.05532 (2019) - [i44]Xi Chen, Amit Levi, Erik Waingarten:
Nearly optimal edge estimation with independent set queries. CoRR abs/1907.04381 (2019) - [i43]Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha:
Efficient average-case population recovery in the presence of insertions and deletions. CoRR abs/1907.05964 (2019) - [i42]Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun:
A Lower Bound on Cycle-Finding in Sparse Digraphs. CoRR abs/1907.12106 (2019) - [i41]Xi Chen, Christos H. Papadimitriou, Tim Roughgarden:
An Axiomatic Approach to Block Rewards. CoRR abs/1909.10645 (2019) - [i40]Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten:
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. CoRR abs/1911.07357 (2019) - [i39]Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, Xinzhi Zhang:
Smoothed complexity of local Max-Cut and binary Max-CSP. CoRR abs/1911.10381 (2019) - [i38]Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten:
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j20]Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The complexity of optimal multidimensional pricing for a unit-demand buyer. Games Econ. Behav. 110: 139-164 (2018) - [j19]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65(6): 40:1-40:18 (2018) - [c46]Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis:
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer. SODA 2018: 2036-2049 - [c45]Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free junta testing. STOC 2018: 749-759 - [i37]Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie:
Distribution-free Junta Testing. CoRR abs/1802.04859 (2018) - 2017
- [j18]Jin-Yi Cai, Xi Chen:
Complexity of Counting CSP with Complex Weights. J. ACM 64(3): 19:1-19:39 (2017) - [j17]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The Complexity of Non-Monotone Markets. J. ACM 64(3): 20:1-20:56 (2017) - [c44]Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM 2017: 37:1-37:20 - [c43]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM 2017: 38:1-38:21 - [c42]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the Query Complexity of Non-Adaptive Junta Testing. CCC 2017: 26:1-26:19 - [c41]Xi Chen, Erik Waingarten, Jinyu Xie:
Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. FOCS 2017: 868-879 - [c40]Xi Chen, Yu Cheng, Bo Tang:
Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games. ITCS 2017: 57:1-57:9 - [c39]Xi Chen, Erik Waingarten, Jinyu Xie:
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. STOC 2017: 523-536 - [c38]Xi Chen, Igor C. Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. STOC 2017: 1232-1245 - [i36]Xi Chen, Erik Waingarten, Jinyu Xie:
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness. CoRR abs/1702.06997 (2017) - [i35]Xi Chen, George Matikas, Dimitris Paparas, Mihalis Yannakakis:
On the Complexity of Bundle-Pricing and Simple Mechanisms. CoRR abs/1702.07032 (2017) - [i34]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. CoRR abs/1704.06314 (2017) - [i33]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten:
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR abs/1706.05556 (2017) - [i32]Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun:
Sample-based high-dimensional convexity testing. CoRR abs/1706.09362 (2017) - [i31]Xi Chen, Erik Waingarten, Jinyu Xie:
Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. CoRR abs/1708.05786 (2017) - [i30]Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j16]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Nonnegative Weighted #CSP: An Effective Complexity Dichotomy. SIAM J. Comput. 45(6): 2177-2198 (2016) - [c37]Xi Chen, Yu Cheng, Bo Tang:
On the Recursive Teaching Dimension of VC Classes. NIPS 2016: 2164-2171 - [c36]Xi Chen, Jinyu Xie:
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. SODA 2016: 54-71 - [c35]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. STOC 2016: 612-625 - [r5]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Complexity Dichotomies for Counting Graph Homomorphisms. Encyclopedia of Algorithms 2016: 366-369 - [r4]Xi Chen, Xiaotie Deng:
Non-approximability of Bimatrix Nash Equilibria. Encyclopedia of Algorithms 2016: 1412-1414 - [i29]Xi Chen, Yu Cheng, Bo Tang:
A Note on Teaching for VC Classes. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c34]Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. FOCS 2015: 1464-1479 - [c33]Xi Chen, David Durfee, Anthi Orfanou:
On the Complexity of Nash Equilibria in Anonymous Games. STOC 2015: 381-390 - [c32]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries. STOC 2015: 519-528 - [i28]Xi Chen, Igor C. Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. CoRR abs/1508.03061 (2015) - [i27]Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Near-optimal small-depth lower bounds for small distance connectivity. CoRR abs/1509.07476 (2015) - [i26]Xi Chen, Yu Cheng, Bo Tang:
Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games. CoRR abs/1511.00785 (2015) - [i25]Xi Chen, Jinyu Xie:
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. CoRR abs/1511.03333 (2015) - [i24]Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio:
Addition is exponentially harder than counting for shallow monotone circuits. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c31]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New Algorithms and Lower Bounds for Monotonicity Testing. FOCS 2014: 286-295 - [c30]Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The Complexity of Optimal Multidimensional Pricing. SODA 2014: 1319-1328 - [i23]Xi Chen, Rocco A. Servedio, Li-Yang Tan:
New algorithms and lower bounds for monotonicity testing. CoRR abs/1412.5655 (2014) - [i22]Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan:
Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries. CoRR abs/1412.5657 (2014) - [i21]Xi Chen, David Durfee, Anthi Orfanou:
On the Complexity of Nash Equilibria in Anonymous Games. CoRR abs/1412.5681 (2014) - 2013
- [j15]Jin-Yi Cai, Xi Chen, Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. SIAM J. Comput. 42(3): 924-1029 (2013) - [j14]Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
How to Compress Interactive Communication. SIAM J. Comput. 42(3): 1327-1363 (2013) - [c29]László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes:
Faster Canonical Forms for Strongly Regular Graphs. FOCS 2013: 157-166 - [c28]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The complexity of non-monotone markets. STOC 2013: 181-190 - [c27]Xi Chen, Xiaorui Sun, Shang-Hua Teng:
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. STOC 2013: 271-280 - [i20]Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The Complexity of Optimal Multidimensional Pricing. CoRR abs/1311.2138 (2013) - 2012
- [c26]Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu:
Inapproximability after Uniqueness Phase Transition in Two-Spin Systems. COCOA 2012: 336-347 - [c25]Jin-Yi Cai, Xi Chen:
Complexity of counting CSP with complex weights. STOC 2012: 909-920 - [i19]Jin-Yi Cai, Xi Chen, Heng Guo, Pinyan Lu:
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems. CoRR abs/1205.2934 (2012) - [i18]Xi Chen, Dimitris Paparas, Mihalis Yannakakis:
The Complexity of Non-Monotone Markets. CoRR abs/1211.4918 (2012) - 2011
- [j13]Xi Chen, Xiaotie Deng, Becky Jie Liu:
On Incentive Compatible Competitive Selection Protocols. Algorithmica 61(2): 447-462 (2011) - [j12]Xi Chen, Neeraj Kayal, Avi Wigderson:
Partial Derivatives in Arithmetic Complexity and Beyond. Found. Trends Theor. Comput. Sci. 6(1-2): 1-138 (2011) - [c24]Jin-yi Cai, Xi Chen, Pinyan Lu:
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. CCC 2011: 45-54 - [c23]Xi Chen, Shang-Hua Teng:
A Complexity View of Markets with Social Influence. ICS 2011: 141-154 - [i17]Jin-yi Cai, Xi Chen:
Complexity of Counting CSP with Complex Weights. CoRR abs/1111.2384 (2011) - 2010
- [j10]Xi Chen, Xiaoming Sun, Shang-Hua Teng:
Quantum Separation of Local Search and Fixed Point Computation. Algorithmica 56(3): 364-382 (2010) - [j9]Jin-yi Cai, Xi Chen, Dong Li:
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. Comput. Complex. 19(1): 37-56 (2010) - [c22]Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng:
On the complexity of equilibria in markets with additively separable utilities. BQGT 2010: 61:1 - [c21]Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu:
On Tractable Exponential Sums. FAW 2010: 148-159 - [c20]Jin-yi Cai, Xi Chen:
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. FOCS 2010: 437-446 - [c19]Jin-yi Cai, Xi Chen, Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. ICALP (1) 2010: 275-286 - [c18]Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
How to compress interactive communication. STOC 2010: 67-76 - [i16]Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu:
On Tractable Exponential Sums. CoRR abs/1005.2632 (2010) - [i15]Jin-yi Cai, Xi Chen:
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. CoRR abs/1008.0915 (2010) - [i14]Xi Chen, Shang-Hua Teng:
A Complexity View of Markets with Social Influence. CoRR abs/1009.0309 (2010) - [i13]Jin-yi Cai, Xi Chen, Pinyan Lu:
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy. CoRR abs/1012.5659 (2010) - 2009
- [j8]Xi Chen, Xiaotie Deng:
A Simplicial Approach for Discrete Fixed Point Theorems. Algorithmica 53(2): 250-262 (2009) - [j7]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): 14:1-14:57 (2009) - [j6]Xi Chen, Li-Sha Huang, Shang-Hua Teng:
Market equilibria with hybrid linear-Leontief utilities. Theor. Comput. Sci. 410(17): 1573-1580 (2009) - [j5]Xi Chen, Xiaotie Deng:
On the complexity of 2D discrete fixed point problem. Theor. Comput. Sci. 410(44): 4448-4456 (2009) - [c17]Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng:
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. FOCS 2009: 273-282 - [c16]Xi Chen, Shang-Hua Teng:
Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. ISAAC 2009: 647-656 - [i12]Jin-yi Cai, Xi Chen, Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. CoRR abs/0903.4728 (2009) - [i11]Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng:
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. CoRR abs/0904.0644 (2009) - [i10]Xi Chen, Shang-Hua Teng:
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria. CoRR abs/0907.4130 (2009) - [i9]Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
Direct Sums in Randomized Communication Complexity. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j4]Xi Chen, Xiaotie Deng:
Matching algorithmic bounds for finding a Brouwer fixed point. J. ACM 55(3): 13:1-13:26 (2008) - [c15]Xi Chen, Xiaoming Sun, Shang-Hua Teng:
Quantum Separation of Local Search and Fixed Point Computation. COCOON 2008: 170-179 - [c14]Jin-yi Cai, Xi Chen, Dong Li:
A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. STOC 2008: 491-498 - [r3]Xi Chen, Xiaotie Deng:
Complexity of Bimatrix Nash Equilibria. Encyclopedia of Algorithms 2008 - [r2]Xi Chen, Xiaotie Deng:
Incentive Compatible Selection. Encyclopedia of Algorithms 2008 - [r1]Xi Chen, Xiaotie Deng:
Non-approximability of Bimatrix Nash Equilibria. Encyclopedia of Algorithms 2008 - 2007
- [j3]Xi Chen, Xiaotie Deng:
Recent development in computational complexity characterization of Nash equilibrium. Comput. Sci. Rev. 1(2): 88-99 (2007) - [j2]Yongxi Cheng, Xi Chen, Yiqun Lisa Yin:
On searching a table consistent with division poset. Theor. Comput. Sci. 370(1-3): 240-253 (2007) - [j1]Lan Liu, Xi Chen, Jing Xiao, Tao Jiang:
Complexity and approximation of the minimum recombinant haplotype configuration problem. Theor. Comput. Sci. 378(3): 316-330 (2007) - [c13]Jing Zhang, Xi Chen, Ming Li:
Computing Exact p-Value for Structured Motif. CPM 2007: 162-172 - [c12]Xi Chen, Shang-Hua Teng:
Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. FOCS 2007: 124-134 - [c11]Xi Chen, Shang-Hua Teng, Paul Valiant:
The approximation complexity of win-lose games. SODA 2007: 159-168 - [i8]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Settling the Complexity of Computing Two-Player Nash Equilibria. CoRR abs/0704.1678 (2007) - [i7]Xi Chen, Shang-Hua Teng:
Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation. CoRR abs/cs/0702088 (2007) - 2006
- [c10]Xi Chen, Xiaotie Deng:
Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set. AAIM 2006: 53-63 - [c9]Xi Chen, Xiaotie Deng:
A Simplicial Approach for Discrete Fixed Point Theorems. COCOON 2006: 3-12 - [c8]Xi Chen, Xiaotie Deng, Becky Jie Liu:
On Incentive Compatible Competitive Selection Protocol. COCOON 2006: 13-22 - [c7]Xi Chen, Xiaotie Deng:
Settling the Complexity of Two-Player Nash Equilibrium. FOCS 2006: 261-272 - [c6]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Computing Nash Equilibria: Approximation and Smoothed Complexity. FOCS 2006: 603-612 - [c5]Xi Chen, Xiaotie Deng:
On the Complexity of 2D Discrete Fixed Point Problem. ICALP (1) 2006: 489-500 - [c4]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Sparse Games Are Hard. WINE 2006: 262-273 - [c3]Xi Chen, Li-Sha Huang, Shang-Hua Teng:
Market Equilibria with Hybrid Linear-Leontief Utilities. WINE 2006: 274-285 - [i6]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Computing Nash Equilibria: Approximation and Smoothed Complexity. CoRR abs/cs/0602043 (2006) - [i5]Xi Chen, Xiaotie Deng:
On the Complexity of 2D Discrete Fixed Point Problem. Electron. Colloquium Comput. Complex. TR06 (2006) - [i4]Xi Chen, Xiaotie Deng, Shang-Hua Teng:
Computing Nash Equilibria: Approximation and Smoothed Complexity. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c2]Lan Liu, Xi Chen, Jing Xiao, Tao Jiang:
Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem. ISAAC 2005: 370-379 - [c1]Xi Chen, Xiaotie Deng:
On algorithms for discrete and approximate brouwer fixed points. STOC 2005: 323-330 - [i3]Yongxi Cheng, Xi Chen, Yiqun Lisa Yin:
On Searching a Table Consistent with Division Poset. CoRR abs/cs/0505075 (2005) - [i2]Xi Chen, Xiaotie Deng:
3-NASH is PPAD-Complete. Electron. Colloquium Comput. Complex. TR05 (2005) - [i1]Xi Chen, Xiaotie Deng:
Settling the Complexity of 2-Player Nash-Equilibrium. Electron. Colloquium Comput. Complex. TR05 (2005)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-05-10 21:32 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint