% csauthors.net - beta - BibTeX bibliography of Xi Chen 001
@inproceedings{conf/isaac/LiuCXJ05,
title = {Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.},
year = {2005},
booktitle = {ISAAC},
author = {{Lan Liu 001} and {Xi Chen 001} and {Jing Xiao} and {Tao Jiang 001}},
publisher = {Springer},
booktitle = {Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings}
}
@inproceedings{conf/stoc/ChenD05,
title = {On algorithms for discrete and approximate brouwer fixed points.},
year = {2005},
booktitle = {STOC},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {ACM},
booktitle = {Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}
}
@article{journals/eccc/ECCC-TR05-134,
title = {3-NASH is PPAD-Complete},
year = {2005},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@article{journals/eccc/ECCC-TR05-140,
title = {Settling the Complexity of 2-Player Nash-Equilibrium},
year = {2005},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@inproceedings{conf/aaim/ChenD06,
title = {Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set.},
year = {2006},
booktitle = {AAIM},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {Springer},
booktitle = {Algorithmic Aspects in Information and Management, Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006, Proceedings}
}
@inproceedings{conf/cocoon/ChenDL06,
title = {On Incentive Compatible Competitive Selection Protocol.},
year = {2006},
booktitle = {COCOON},
author = {{Xi Chen 001} and {Xiaotie Deng} and {Becky Jie Liu}},
publisher = {Springer},
booktitle = {Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings}
}
@inproceedings{conf/focs/ChenD06,
title = {Settling the Complexity of Two-Player Nash Equilibrium.},
year = {2006},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {IEEE Computer Society},
booktitle = {47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings}
}
@inproceedings{conf/wine/ChenDT06,
title = {Sparse Games Are Hard.},
year = {2006},
booktitle = {WINE},
author = {{Xi Chen 001} and {Xiaotie Deng} and {Shang-Hua Teng}},
publisher = {Springer},
booktitle = {Internet and Network Economics, Second International Workshop, WINE 2006, Patras, Greece, December 15-17, 2006, Proceedings}
}
@article{journals/eccc/ChenDT06,
title = {Computing Nash Equilibria: Approximation and Smoothed Complexity.},
year = {2006},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Xiaotie Deng} and {Shang-Hua Teng}}
}
@inproceedings{conf/cpm/ZhangCL07,
title = {Computing Exact p-Value for Structured Motif.},
year = {2007},
booktitle = {CPM},
author = {{Jing Zhang 012} and {Xi Chen 001} and {Ming Li 001}},
publisher = {Springer},
booktitle = {Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings}
}
@inproceedings{conf/focs/ChenT07,
title = {Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation.},
year = {2007},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Shang-Hua Teng}},
publisher = {IEEE Computer Society},
booktitle = {48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings}
}
@inproceedings{conf/soda/ChenTV07,
title = {The approximation complexity of win-lose games.},
year = {2007},
booktitle = {SODA},
author = {{Xi Chen 001} and {Shang-Hua Teng} and {Paul Valiant}},
publisher = {SIAM},
booktitle = {Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007}
}
@article{journals/corr/abs-cs-0702088,
title = {Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation},
year = {2007},
journal = {CoRR},
author = {{Xi Chen 001} and {Shang-Hua Teng}}
}
@article{journals/csr/ChenD07,
title = {Recent development in computational complexity characterization of Nash equilibrium.},
year = {2007},
journal = {Comput. Sci. Rev.},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@article{journals/tcs/ChengCY07,
title = {On searching a table consistent with division poset.},
year = {2007},
journal = {Theor. Comput. Sci.},
author = {{Yongxi Cheng} and {Xi Chen 001} and {Yiqun Lisa Yin}}
}
@article{journals/tcs/LiuXXJ07,
title = {Complexity and approximation of the minimum recombinant haplotype configuration problem.},
year = {2007},
journal = {Theor. Comput. Sci.},
author = {{Lan Liu 001} and {Xi Chen 001} and {Jing Xiao} and {Tao Jiang 001}}
}
@inproceedings{conf/stoc/CaiCL08,
title = {A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.},
year = {2008},
booktitle = {STOC},
author = {{Jin-yi Cai} and {Xi Chen 001} and {Dong Li}},
publisher = {ACM},
booktitle = {Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008}
}
@article{journals/jacm/ChenD08,
title = {Matching algorithmic bounds for finding a Brouwer fixed point.},
year = {2008},
journal = {J. ACM},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@incollection{reference/algo/ChenD08,
title = {Complexity of Bimatrix Nash Equilibria.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/ChenD08a,
title = {Incentive Compatible Selection.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@incollection{reference/algo/ChenD08b,
title = {Non-approximability of Bimatrix Nash Equilibria.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Xi Chen 001} and {Xiaotie Deng}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@inproceedings{conf/focs/ChenDDT09,
title = {Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.},
year = {2009},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Decheng Dai} and {Ye Du} and {Shang-Hua Teng}},
publisher = {IEEE Computer Society},
booktitle = {50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA}
}
@inproceedings{conf/isaac/ChenT09,
title = {Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.},
year = {2009},
booktitle = {ISAAC},
author = {{Xi Chen 001} and {Shang-Hua Teng}},
publisher = {Springer},
booktitle = {Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings}
}
@article{journals/algorithmica/ChenD09,
title = {A Simplicial Approach for Discrete Fixed Point Theorems.},
year = {2009},
journal = {Algorithmica},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@article{journals/eccc/BarakBCR09,
title = {Direct Sums in Randomized Communication Complexity.},
year = {2009},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Boaz Barak} and {Mark Braverman} and {Xi Chen 001} and {Anup Rao 001}}
}
@article{journals/jacm/ChenDT09,
title = {Settling the complexity of computing two-player Nash equilibria.},
year = {2009},
journal = {J. ACM},
author = {{Xi Chen 001} and {Xiaotie Deng} and {Shang-Hua Teng}}
}
@article{journals/tcs/ChenD09,
title = {On the complexity of 2D discrete fixed point problem.},
year = {2009},
journal = {Theor. Comput. Sci.},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@article{journals/tcs/ChenHT09,
title = {Market equilibria with hybrid linear-Leontief utilities.},
year = {2009},
journal = {Theor. Comput. Sci.},
author = {{Xi Chen 001} and {Li-Sha Huang} and {Shang-Hua Teng}}
}
@inproceedings{conf/bqgt/ChenDDT10,
title = {On the complexity of equilibria in markets with additively separable utilities.},
year = {2010},
booktitle = {BQGT},
author = {{Xi Chen 001} and {Decheng Dai} and {Ye Du} and {Shang-Hua Teng}},
publisher = {ACM},
booktitle = {Proceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions, BQGT '10, Newport Beach, California, USA, May 14-16, 2010}
}
@inproceedings{conf/faw/CaiCLL10,
title = {On Tractable Exponential Sums.},
year = {2010},
booktitle = {FAW},
author = {{Jin-yi Cai} and {Xi Chen 001} and {Richard J. Lipton} and {Pinyan Lu}},
publisher = {Springer},
booktitle = {Frontiers in Algorithmics, 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings}
}
@article{journals/algorithmica/ChenST10,
title = {Quantum Separation of Local Search and Fixed Point Computation.},
year = {2010},
journal = {Algorithmica},
author = {{Xi Chen 001} and {Xiaoming Sun 001} and {Shang-Hua Teng}}
}
@article{journals/cc/CaiCL10,
title = {Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.},
year = {2010},
journal = {Comput. Complex.},
author = {{Jin-yi Cai} and {Xi Chen 001} and {Dong Li}}
}
@article{journals/corr/abs-1012-5659,
title = {Non-negative Weighted #CSPs: An Effective Complexity Dichotomy},
year = {2010},
journal = {CoRR},
author = {{Jin-yi Cai} and {Xi Chen 001} and {Pinyan Lu}}
}
@inproceedings{conf/coco/CaiCL11,
title = {Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.},
year = {2011},
booktitle = {CCC},
author = {{Jin-yi Cai} and {Xi Chen 001} and {Pinyan Lu}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011}
}
@inproceedings{conf/innovations/ChenT11,
title = {A Complexity View of Markets with Social Influence.},
year = {2011},
booktitle = {ICS},
author = {{Xi Chen 001} and {Shang-Hua Teng}},
publisher = {Tsinghua University Press},
booktitle = {Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings}
}
@article{journals/algorithmica/ChenDL11,
title = {On Incentive Compatible Competitive Selection Protocols.},
year = {2011},
journal = {Algorithmica},
author = {{Xi Chen 001} and {Xiaotie Deng} and {Becky Jie Liu}}
}
@article{journals/fttcs/ChenKW11,
title = {Partial Derivatives in Arithmetic Complexity and Beyond.},
year = {2011},
journal = {Found. Trends Theor. Comput. Sci.},
author = {{Xi Chen 001} and {Neeraj Kayal} and {Avi Wigderson}}
}
@article{journals/sigact/Chen11a,
title = {Guest column: complexity dichotomies of counting problems.},
year = {2011},
journal = {SIGACT News},
author = {{Xi Chen 001}}
}
@inproceedings{conf/cocoa/CaiCGL12,
title = {Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.},
year = {2012},
booktitle = {COCOA},
author = {{Jin-Yi Cai} and {Xi Chen 001} and {Heng Guo 001} and {Pinyan Lu}},
publisher = {Springer},
booktitle = {Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings}
}
@inproceedings{conf/focs/BabaiCSTW13,
title = {Faster Canonical Forms for Strongly Regular Graphs.},
year = {2013},
booktitle = {FOCS},
author = {{László Babai} and {Xi Chen 001} and {Xiaorui Sun} and {Shang-Hua Teng} and {John Wilmes}},
publisher = {IEEE Computer Society},
booktitle = {54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA}
}
@inproceedings{conf/stoc/ChenST13,
title = {Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems.},
year = {2013},
booktitle = {STOC},
author = {{Xi Chen 001} and {Xiaorui Sun} and {Shang-Hua Teng}},
publisher = {ACM},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}
}
@article{journals/siamcomp/BarakBCR13,
title = {How to Compress Interactive Communication.},
year = {2013},
journal = {SIAM J. Comput.},
author = {{Boaz Barak} and {Mark Braverman} and {Xi Chen 001} and {Anup Rao 001}}
}
@article{journals/siamcomp/CaiCL13,
title = {Graph Homomorphisms with Complex Values: A Dichotomy Theorem.},
year = {2013},
journal = {SIAM J. Comput.},
author = {{Jin-Yi Cai} and {Xi Chen 001} and {Pinyan Lu}}
}
@inproceedings{conf/focs/ChenST14,
title = {New Algorithms and Lower Bounds for Monotonicity Testing.},
year = {2014},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Rocco A. Servedio} and {Li-Yang Tan}},
publisher = {IEEE Computer Society},
booktitle = {55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014}
}
@inproceedings{conf/soda/ChenDPSY14,
title = {The Complexity of Optimal Multidimensional Pricing.},
year = {2014},
booktitle = {SODA},
author = {{Xi Chen 001} and {Ilias Diakonikolas} and {Dimitris Paparas} and {Xiaorui Sun} and {Mihalis Yannakakis}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}
}
@inproceedings{conf/focs/ChenDOPSY15,
title = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.},
year = {2015},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Ilias Diakonikolas} and {Anthi Orfanou} and {Dimitris Paparas} and {Xiaorui Sun} and {Mihalis Yannakakis}},
publisher = {IEEE Computer Society},
booktitle = {IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015}
}
@inproceedings{conf/stoc/ChenDO15,
title = {On the Complexity of Nash Equilibria in Anonymous Games.},
year = {2015},
booktitle = {STOC},
author = {{Xi Chen 001} and {David Durfee} and {Anthi Orfanou}},
publisher = {ACM},
booktitle = {Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015}
}
@inproceedings{conf/stoc/ChenDST15,
title = {Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries.},
year = {2015},
booktitle = {STOC},
author = {{Xi Chen 001} and {Anindya De} and {Rocco A. Servedio} and {Li-Yang Tan}},
publisher = {ACM},
booktitle = {Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015}
}
@article{journals/corr/ChenCT15,
title = {Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games.},
year = {2015},
journal = {CoRR},
author = {{Xi Chen 001} and {Yu Cheng 002} and {Bo Tang}}
}
@article{journals/eccc/ChenOS15,
title = {Addition is exponentially harder than counting for shallow monotone circuits.},
year = {2015},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Igor Carboni Oliveira} and {Rocco A. Servedio}}
}
@inproceedings{conf/nips/ChenCCT16,
title = {On the Recursive Teaching Dimension of VC Classes.},
year = {2016},
booktitle = {NIPS},
author = {{Xi Chen 001} and {Yu Cheng 002} and {Bo Tang}},
booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain}
}
@inproceedings{conf/soda/ChenX16,
title = {Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.},
year = {2016},
booktitle = {SODA},
author = {{Xi Chen 001} and {Jinyu Xie}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016}
}
@inproceedings{conf/stoc/ChenOST16,
title = {Near-optimal small-depth lower bounds for small distance connectivity.},
year = {2016},
booktitle = {STOC},
author = {{Xi Chen 001} and {Igor C. Oliveira} and {Rocco A. Servedio} and {Li-Yang Tan}},
publisher = {ACM},
booktitle = {Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016}
}
@article{journals/eccc/ChenCT16,
title = {A Note on Teaching for VC Classes.},
year = {2016},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Yu Cheng 002} and {Bo Tang}}
}
@article{journals/siamcomp/CaiCL16,
title = {Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.},
year = {2016},
journal = {SIAM J. Comput.},
author = {{Jin-Yi Cai} and {Xi Chen 001} and {Pinyan Lu}}
}
@incollection{reference/algo/CaiCL16,
title = {Complexity Dichotomies for Counting Graph Homomorphisms.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Jin-Yi Cai} and {Xi Chen 001} and {Pinyan Lu}}
}
@incollection{reference/algo/ChenD16,
title = {Non-approximability of Bimatrix Nash Equilibria.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Xi Chen 001} and {Xiaotie Deng}}
}
@inproceedings{conf/approx/0001FSS17,
title = {Sample-Based High-Dimensional Convexity Testing.},
year = {2017},
booktitle = {APPROX-RANDOM},
author = {{Xi Chen 001} and {Adam Freilich} and {Rocco A. Servedio} and {Timothy Sun}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA}
}
@inproceedings{conf/approx/0001STW17,
title = {Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.},
year = {2017},
booktitle = {APPROX-RANDOM},
author = {{Xi Chen 001} and {Rocco A. Servedio} and {Li-Yang Tan} and {Erik Waingarten}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA}
}
@inproceedings{conf/focs/ChenWX17,
title = {Boolean Unateness Testing with Õ(n3/4) Adaptive Queries.},
year = {2017},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Erik Waingarten} and {Jinyu Xie}},
publisher = {IEEE Computer Society},
booktitle = {58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017}
}
@inproceedings{conf/innovations/ChenCT17,
title = {Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games.},
year = {2017},
booktitle = {ITCS},
author = {{Xi Chen 001} and {Yu Cheng 002} and {Bo Tang}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA}
}
@inproceedings{conf/stoc/ChenWX17,
title = {Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.},
year = {2017},
booktitle = {STOC},
author = {{Xi Chen 001} and {Erik Waingarten} and {Jinyu Xie}},
publisher = {ACM},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017}
}
@article{journals/corr/ChenMPY17,
title = {On the Complexity of Bundle-Pricing and Simple Mechanisms.},
year = {2017},
journal = {CoRR},
author = {{Xi Chen 001} and {George Matikas} and {Dimitris Paparas} and {Mihalis Yannakakis}}
}
@article{journals/jacm/CaiC17,
title = {Complexity of Counting CSP with Complex Weights.},
year = {2017},
journal = {J. ACM},
author = {{Jin-Yi Cai} and {Xi Chen 001}}
}
@article{journals/jacm/ChenPY17,
title = {The Complexity of Non-Monotone Markets.},
year = {2017},
journal = {J. ACM},
author = {{Xi Chen 001} and {Dimitris Paparas} and {Mihalis Yannakakis}}
}
@inproceedings{conf/soda/ChenMPY18,
title = {On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.},
year = {2018},
booktitle = {SODA},
author = {{Xi Chen 001} and {George Matikas} and {Dimitris Paparas} and {Mihalis Yannakakis}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018}
}
@article{journals/geb/ChenDPSY18,
title = {The complexity of optimal multidimensional pricing for a unit-demand buyer.},
year = {2018},
journal = {Games Econ. Behav.},
author = {{Xi Chen 001} and {Ilias Diakonikolas} and {Dimitris Paparas} and {Xiaorui Sun} and {Mihalis Yannakakis}}
}
@article{journals/jacm/ChenSTWX18,
title = {Settling the Query Complexity of Non-adaptive Junta Testing.},
year = {2018},
journal = {J. ACM},
author = {{Xi Chen 001} and {Rocco A. Servedio} and {Li-Yang Tan} and {Erik Waingarten} and {Jinyu Xie}}
}
@inproceedings{conf/aft/ChenPR19,
title = {An Axiomatic Approach to Block Rewards.},
year = {2019},
booktitle = {AFT},
author = {{Xi Chen 001} and {Christos H. Papadimitriou} and {Tim Roughgarden}},
publisher = {ACM},
booktitle = {Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019.}
}
@inproceedings{conf/approx/Ban0SS19,
title = {Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.},
year = {2019},
booktitle = {APPROX-RANDOM},
author = {{Frank Ban} and {Xi Chen 001} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA.}
}
@inproceedings{conf/focs/Ban0FSS19,
title = {Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.},
year = {2019},
booktitle = {FOCS},
author = {{Frank Ban} and {Xi Chen 001} and {Adam Freilich} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {IEEE Computer Society},
booktitle = {60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019}
}
@inproceedings{conf/stoc/ChenW19,
title = {Testing unateness nearly optimally.},
year = {2019},
booktitle = {STOC},
author = {{Xi Chen 001} and {Erik Waingarten}},
publisher = {ACM},
booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019.}
}
@article{journals/cc/CaiC19,
title = {A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.},
year = {2019},
journal = {Comput. Complex.},
author = {{Jin-Yi Cai} and {Xi Chen 001}}
}
@article{journals/eccc/CanonneCKLW19,
title = {Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.},
year = {2019},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Clément L. Canonne} and {Xi Chen 001} and {Gautam Kamath 001} and {Amit Levi} and {Erik Waingarten}}
}
@article{journals/talg/LiuCSSX19,
title = {Distribution-free Junta Testing.},
year = {2019},
journal = {ACM Trans. Algorithms},
author = {{Zhengyang Liu 002} and {Xi Chen 001} and {Rocco A. Servedio} and {Ying Sheng 004} and {Jinyu Xie}}
}
@inproceedings{conf/nips/ChenP20,
title = {Hedging in games: Faster convergence of external and swap regrets.},
year = {2020},
booktitle = {NeurIPS},
author = {{Xi Chen 001} and {Binghui Peng}},
booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual.}
}
@inproceedings{conf/soda/0001LW20,
title = {Nearly optimal edge estimation with independent set queries.},
year = {2020},
booktitle = {SODA},
author = {{Xi Chen 001} and {Amit Levi} and {Erik Waingarten}},
publisher = {SIAM},
booktitle = {Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020.}
}
@inproceedings{conf/stoc/ChenGVYZ20,
title = {Smoothed complexity of local max-cut and binary max-CSP.},
year = {2020},
booktitle = {STOC},
author = {{Xi Chen 001} and {Chenghao Guo} and {Emmanouil-Vasileios Vlatakis-Gkaragkounis} and {Mihalis Yannakakis} and {Xinzhi Zhang 002}},
publisher = {ACM},
booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020}
}
@article{journals/corr/abs-2004-12496,
title = {Learning and Testing Junta Distributions with Subcube Conditioning.},
year = {2020},
journal = {CoRR},
author = {{Xi Chen 001} and {Rajesh Jayaram} and {Amit Levi} and {Erik Waingarten}}
}
@inproceedings{conf/colt/ChenJLW21,
title = {Learning and testing junta distributions with sub cube conditioning.},
year = {2021},
booktitle = {COLT},
author = {{Xi Chen 001} and {Rajesh Jayaram} and {Amit Levi} and {Erik Waingarten}},
publisher = {PMLR},
booktitle = {Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA.}
}
@inproceedings{conf/innovations/0001DLSS21,
title = {Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.},
year = {2021},
booktitle = {ITCS},
author = {{Xi Chen 001} and {Anindya De} and {Chin Ho Lee} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference.}
}
@inproceedings{conf/sigecom/ChenKK21,
title = {The Complexity of Pacing for Second-Price Auctions.},
year = {2021},
booktitle = {EC},
author = {{Xi Chen 001} and {Christian Kroer} and {Rachitesh Kumar}},
publisher = {ACM},
booktitle = {EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021}
}
@inproceedings{conf/soda/ChenDLSS21,
title = {Polynomial-time trace reconstruction in the smoothed complexity model.},
year = {2021},
booktitle = {SODA},
author = {{Xi Chen 001} and {Anindya De} and {Chin Ho Lee} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/wine/ChenKK21,
title = {Throttling Equilibria in Auction Markets.},
year = {2021},
booktitle = {WINE},
author = {{Xi Chen 001} and {Christian Kroer} and {Rachitesh Kumar}},
publisher = {Springer},
booktitle = {Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings}
}
@inproceedings{conf/focs/ChenPP22,
title = {Memory Bounds for Continual Learning.},
year = {2022},
booktitle = {FOCS},
author = {{Xi Chen 001} and {Christos H. Papadimitriou} and {Binghui Peng}},
publisher = {IEEE},
booktitle = {63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022}
}
@inproceedings{conf/sigecom/ChenL22,
title = {Improved Upper Bounds for Finding Tarski Fixed Points.},
year = {2022},
booktitle = {EC},
author = {{Xi Chen 001} and {Yuhao Li 002}},
publisher = {ACM},
booktitle = {EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022}
}
@inproceedings{conf/soda/ChenCPY22,
title = {Computational Hardness of the Hylland-Zeckhauser Scheme.},
year = {2022},
booktitle = {SODA},
author = {{Thomas Chen} and {Xi Chen 001} and {Binghui Peng} and {Mihalis Yannakakis}},
publisher = {SIAM},
booktitle = {Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022}
}
@inproceedings{conf/soda/ChenDLSS22,
title = {Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.},
year = {2022},
booktitle = {SODA},
author = {{Xi Chen 001} and {Anindya De} and {Chin Ho Lee} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {SIAM},
booktitle = {Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022}
}
@inproceedings{conf/soda/ChenJRS22,
title = {Average-Case Subset Balancing Problems.},
year = {2022},
booktitle = {SODA},
author = {{Xi Chen 001} and {Yaonan Jin} and {Tim Randolph 001} and {Rocco A. Servedio}},
publisher = {SIAM},
booktitle = {Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022}
}
@inproceedings{conf/stoc/ChenJLW22,
title = {New streaming algorithms for high dimensional EMD and MST.},
year = {2022},
booktitle = {STOC},
author = {{Xi Chen 001} and {Rajesh Jayaram} and {Amit Levi} and {Erik Waingarten}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@inproceedings{conf/stoc/ChenP22,
title = {On the complexity of dynamic submodular maximization.},
year = {2022},
booktitle = {STOC},
author = {{Xi Chen 001} and {Binghui Peng}},
publisher = {ACM},
booktitle = {STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}
}
@article{journals/corr/abs-2211-01000,
title = {SoK: Play-to-Earn Projects.},
year = {2022},
journal = {CoRR},
author = {{Jingfan Yu} and {Mengqian Zhang} and {Xi Chen 001} and {Zhixuan Fang}}
}
@article{journals/siamcomp/ChenDOPSY22,
title = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.},
year = {2022},
journal = {SIAM J. Comput.},
author = {{Xi Chen 001} and {Ilias Diakonikolas} and {Anthi Orfanou} and {Dimitris Paparas} and {Xiaorui Sun} and {Mihalis Yannakakis}}
}
@article{journals/talg/ChenRSS22,
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs.},
year = {2022},
journal = {ACM Trans. Algorithms},
author = {{Xi Chen 001} and {Tim Randolph 001} and {Rocco A. Servedio} and {Timothy Sun}}
}
@inproceedings{conf/approx/0001J0S23,
title = {Subset Sum in Time 2n/2 / poly(n).},
year = {2023},
booktitle = {APPROX/RANDOM},
author = {{Xi Chen 001} and {Yaonan Jin} and {Tim Randolph 001} and {Rocco A. Servedio}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA}
}
@inproceedings{conf/soda/0001DLSS23,
title = {Approximate Trace Reconstruction from a Single Trace.},
year = {2023},
booktitle = {SODA},
author = {{Xi Chen 001} and {Anindya De} and {Chin Ho Lee} and {Rocco A. Servedio} and {Sandip Sinha}},
publisher = {SIAM},
booktitle = {Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023}
}
@inproceedings{conf/stoc/ChenCJLW23,
title = {Streaming Euclidean MST to a Constant Factor.},
year = {2023},
booktitle = {STOC},
author = {{Xi Chen 001} and {Vincent Cohen-Addad} and {Rajesh Jayaram} and {Amit Levi} and {Erik Waingarten}},
publisher = {ACM},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023}
}
@inproceedings{conf/stoc/ChenP23,
title = {Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.},
year = {2023},
booktitle = {STOC},
author = {{Xi Chen 001} and {Binghui Peng}},
publisher = {ACM},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023}
}
@article{journals/corr/abs-2305-15804,
title = {Smoothed Complexity of SWAP in Local Graph Partitioning.},
year = {2023},
journal = {CoRR},
author = {{Xi Chen 001} and {Chenghao Guo} and {Emmanouil-Vasileios Vlatakis-Gkaragkounis} and {Mihalis Yannakakis}}
}
@article{journals/corr/abs-2306-12534,
title = {Memory-Query Tradeoffs for Randomized Convex Optimization.},
year = {2023},
journal = {CoRR},
author = {{Xi Chen 001} and {Binghui Peng}}
}
@article{journals/corr/abs-2309-12513,
title = {Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.},
year = {2023},
journal = {CoRR},
author = {{Xi Chen 001} and {Anindya De} and {Yuhao Li 002} and {Shivam Nadimpalli} and {Rocco A. Servedio}}
}
@article{journals/eccc/ChenLY23,
title = {Reducing Tarski to Unique Tarski (in the Black-box Model).},
year = {2023},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Xi Chen 001} and {Yuhao Li 002} and {Mihalis Yannakakis}}
}
@inproceedings{conf/innovations/0001D0NS24,
title = {Testing Intersecting and Union-Closed Families.},
year = {2024},
booktitle = {ITCS},
author = {{Xi Chen 001} and {Anindya De} and {Yuhao Li 002} and {Shivam Nadimpalli} and {Rocco A. Servedio}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA}
}
@article{journals/corr/abs-2401-07242,
title = {Testing Sumsets is Hard.},
year = {2024},
journal = {CoRR},
author = {{Xi Chen 001} and {Shivam Nadimpalli} and {Tim Randolph 001} and {Rocco A. Servedio} and {Or Zamir}}
}