Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Xi Chen 0001
@inproceedings{DBLP:conf/innovations/0001D0NS24,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {Venkatesan Guruswami},
title = {Testing Intersecting and Union-Closed Families},
booktitle = {15th Innovations in Theoretical Computer Science Conference, {ITCS}
2024, January 30 to February 2, 2024, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {287},
pages = {33:1--33:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2024.33},
doi = {10.4230/LIPICS.ITCS.2024.33},
timestamp = {Wed, 24 Jan 2024 15:25:09 +0100},
biburl = {https://dblp.org/rec/conf/innovations/0001D0NS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLNS24,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
editor = {David P. Woodruff},
title = {Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {4321--4337},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.151},
doi = {10.1137/1.9781611977912.151},
timestamp = {Thu, 04 Apr 2024 19:38:10 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLNS24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenM24,
author = {Xi Chen and
Cassandra Marcussen},
editor = {David P. Woodruff},
title = {Uniformity Testing over Hypergrids with Subcube Conditioning},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {4338--4370},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.152},
doi = {10.1137/1.9781611977912.152},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenM24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenGVY24,
author = {Xi Chen and
Chenghao Guo and
Emmanouil V. Vlatakis{-}Gkaragkounis and
Mihalis Yannakakis},
editor = {David P. Woodruff},
title = {Smoothed Complexity of {SWAP} in Local Graph Partitioning},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {5057--5083},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.182},
doi = {10.1137/1.9781611977912.182},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenGVY24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2401-07242,
author = {Xi Chen and
Shivam Nadimpalli and
Tim Randolph and
Rocco A. Servedio and
Or Zamir},
title = {Testing Sumsets is Hard},
journal = {CoRR},
volume = {abs/2401.07242},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2401.07242},
doi = {10.48550/ARXIV.2401.07242},
eprinttype = {arXiv},
eprint = {2401.07242},
timestamp = {Thu, 01 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2401-07242.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/00010Y24,
author = {Xi Chen and
Yuhao Li and
Mihalis Yannakakis},
title = {Computing a Fixed Point of Contraction Maps in Polynomial Queries},
journal = {Electron. Colloquium Comput. Complex.},
pages = {TR24--057},
year = {2024},
url = {https://eccc.weizmann.ac.il/report/2024/057},
timestamp = {Tue, 02 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/00010Y24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001J0S23,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
editor = {Nicole Megow and
Adam D. Smith},
title = {Subset Sum in Time 2\({}^{\mbox{n/2}}\) / poly(n)},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2023, September 11-13, 2023, Atlanta,
Georgia, {USA}},
series = {LIPIcs},
volume = {275},
pages = {39:1--39:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.39},
doi = {10.4230/LIPICS.APPROX/RANDOM.2023.39},
timestamp = {Sat, 09 Sep 2023 00:04:38 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001J0S23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/0001LY23,
author = {Xi Chen and
Yuhao Li and
Mihalis Yannakakis},
editor = {Amnon Ta{-}Shma},
title = {Reducing Tarski to Unique Tarski (In the Black-Box Model)},
booktitle = {38th Computational Complexity Conference, {CCC} 2023, July 17-20,
2023, Warwick, {UK}},
series = {LIPIcs},
volume = {264},
pages = {21:1--21:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.CCC.2023.21},
doi = {10.4230/LIPICS.CCC.2023.21},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/0001LY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/0001DLSS23,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {Nikhil Bansal and
Viswanath Nagarajan},
title = {Approximate Trace Reconstruction from a Single Trace},
booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2023, Florence, Italy, January 22-25, 2023},
pages = {605--637},
publisher = {{SIAM}},
year = {2023},
url = {https://doi.org/10.1137/1.9781611977554.ch27},
doi = {10.1137/1.9781611977554.CH27},
timestamp = {Fri, 17 Feb 2023 09:28:57 +0100},
biburl = {https://dblp.org/rec/conf/soda/0001DLSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenCJLW23,
author = {Xi Chen and
Vincent Cohen{-}Addad and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Streaming Euclidean {MST} to a Constant Factor},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {156--169},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585168},
doi = {10.1145/3564246.3585168},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenCJLW23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenP23,
author = {Xi Chen and
Binghui Peng},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Complexity of Equilibria in First-Price Auctions under General Tie-Breaking
Rules},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {698--709},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585195},
doi = {10.1145/3564246.3585195},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenP23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2301-07134,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
title = {Subset Sum in Time 2\({}^{\mbox{n/2}}\)/poly(n)},
journal = {CoRR},
volume = {abs/2301.07134},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2301.07134},
doi = {10.48550/ARXIV.2301.07134},
eprinttype = {arXiv},
eprint = {2301.07134},
timestamp = {Mon, 30 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2301-07134.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2303-16388,
author = {Xi Chen and
Binghui Peng},
title = {Complexity of Equilibria in First-Price Auctions under General Tie-Breaking
Rules},
journal = {CoRR},
volume = {abs/2303.16388},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2303.16388},
doi = {10.48550/ARXIV.2303.16388},
eprinttype = {arXiv},
eprint = {2303.16388},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2303-16388.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2305-15804,
author = {Xi Chen and
Chenghao Guo and
Emmanouil V. Vlatakis{-}Gkaragkounis and
Mihalis Yannakakis},
title = {Smoothed Complexity of {SWAP} in Local Graph Partitioning},
journal = {CoRR},
volume = {abs/2305.15804},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2305.15804},
doi = {10.48550/ARXIV.2305.15804},
eprinttype = {arXiv},
eprint = {2305.15804},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2305-15804.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2306-12534,
author = {Xi Chen and
Binghui Peng},
title = {Memory-Query Tradeoffs for Randomized Convex Optimization},
journal = {CoRR},
volume = {abs/2306.12534},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2306.12534},
doi = {10.48550/ARXIV.2306.12534},
eprinttype = {arXiv},
eprint = {2306.12534},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2306-12534.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2309-12513,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas},
journal = {CoRR},
volume = {abs/2309.12513},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2309.12513},
doi = {10.48550/ARXIV.2309.12513},
eprinttype = {arXiv},
eprint = {2309.12513},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2309-12513.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2311-11119,
author = {Xi Chen and
Anindya De and
Yuhao Li and
Shivam Nadimpalli and
Rocco A. Servedio},
title = {Testing Intersecting and Union-Closed Families},
journal = {CoRR},
volume = {abs/2311.11119},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.11119},
doi = {10.48550/ARXIV.2311.11119},
eprinttype = {arXiv},
eprint = {2311.11119},
timestamp = {Thu, 23 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-11119.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenLY23,
author = {Xi Chen and
Yuhao Li and
Mihalis Yannakakis},
title = {Reducing Tarski to Unique Tarski (in the Black-box Model)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-073}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/073},
eprinttype = {ECCC},
eprint = {TR23-073},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenLY23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChenDOPSY22,
author = {Xi Chen and
Ilias Diakonikolas and
Anthi Orfanou and
Dimitris Paparas and
Xiaorui Sun and
Mihalis Yannakakis},
title = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms
for a Unit-Demand Buyer},
journal = {{SIAM} J. Comput.},
volume = {51},
number = {3},
pages = {492--548},
year = {2022},
url = {https://doi.org/10.1137/17m1136481},
doi = {10.1137/17M1136481},
timestamp = {Mon, 27 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChenDOPSY22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/ChenRSS22,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
journal = {{ACM} Trans. Algorithms},
volume = {18},
number = {4},
pages = {31:1--31:23},
year = {2022},
url = {https://doi.org/10.1145/3417979},
doi = {10.1145/3417979},
timestamp = {Mon, 05 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/ChenRSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenPP22,
author = {Xi Chen and
Christos H. Papadimitriou and
Binghui Peng},
title = {Memory Bounds for Continual Learning},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {519--530},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00056},
doi = {10.1109/FOCS54457.2022.00056},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/ChenPP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigecom/ChenL22,
author = {Xi Chen and
Yuhao Li},
editor = {David M. Pennock and
Ilya Segal and
Sven Seuken},
title = {Improved Upper Bounds for Finding Tarski Fixed Points},
booktitle = {{EC} '22: The 23rd {ACM} Conference on Economics and Computation,
Boulder, CO, USA, July 11 - 15, 2022},
pages = {1108--1118},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3490486.3538297},
doi = {10.1145/3490486.3538297},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/sigecom/ChenL22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenJRS22,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Average-Case Subset Balancing Problems},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {743--778},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.33},
doi = {10.1137/1.9781611977073.33},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenJRS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLSS22,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Near-Optimal Average-Case Approximate Trace Reconstruction from Few
Traces},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {779--821},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.34},
doi = {10.1137/1.9781611977073.34},
timestamp = {Tue, 12 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenCPY22,
author = {Thomas Chen and
Xi Chen and
Binghui Peng and
Mihalis Yannakakis},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {Computational Hardness of the Hylland-Zeckhauser Scheme},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {2253--2268},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.90},
doi = {10.1137/1.9781611977073.90},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenCPY22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenJLW22,
author = {Xi Chen and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {New streaming algorithms for high dimensional {EMD} and {MST}},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {222--233},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519979},
doi = {10.1145/3519935.3519979},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenJLW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenP22,
author = {Xi Chen and
Binghui Peng},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {On the complexity of dynamic submodular maximization},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {1685--1698},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3519951},
doi = {10.1145/3519935.3519951},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenP22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2202-05913,
author = {Xi Chen and
Yuhao Li},
title = {Improved Upper Bounds for Finding Tarski Fixed Points},
journal = {CoRR},
volume = {abs/2202.05913},
year = {2022},
url = {https://arxiv.org/abs/2202.05913},
eprinttype = {arXiv},
eprint = {2202.05913},
timestamp = {Wed, 04 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2202-05913.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2204-10830,
author = {Xi Chen and
Christos H. Papadimitriou and
Binghui Peng},
title = {Memory Bounds for Continual Learning},
journal = {CoRR},
volume = {abs/2204.10830},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2204.10830},
doi = {10.48550/ARXIV.2204.10830},
eprinttype = {arXiv},
eprint = {2204.10830},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2204-10830.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-01000,
author = {Jingfan Yu and
Mengqian Zhang and
Xi Chen and
Zhixuan Fang},
title = {SoK: Play-to-Earn Projects},
journal = {CoRR},
volume = {abs/2211.01000},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.01000},
doi = {10.48550/ARXIV.2211.01000},
eprinttype = {arXiv},
eprint = {2211.01000},
timestamp = {Thu, 28 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-01000.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-03292,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Approximate Trace Reconstruction from a Single Trace},
journal = {CoRR},
volume = {abs/2211.03292},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.03292},
doi = {10.48550/ARXIV.2211.03292},
eprinttype = {arXiv},
eprint = {2211.03292},
timestamp = {Mon, 30 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-03292.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-06546,
author = {Vincent Cohen{-}Addad and
Xi Chen and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
title = {Streaming Euclidean {MST} to a Constant Factor},
journal = {CoRR},
volume = {abs/2212.06546},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.06546},
doi = {10.48550/ARXIV.2212.06546},
eprinttype = {arXiv},
eprint = {2212.06546},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-06546.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/ChenJLW21,
author = {Xi Chen and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
editor = {Mikhail Belkin and
Samory Kpotufe},
title = {Learning and testing junta distributions with sub cube conditioning},
booktitle = {Conference on Learning Theory, {COLT} 2021, 15-19 August 2021, Boulder,
Colorado, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {134},
pages = {1060--1113},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v134/chen21b.html},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/colt/ChenJLW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/0001DLSS21,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {James R. Lee},
title = {Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime},
booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
2021, January 6-8, 2021, Virtual Conference},
series = {LIPIcs},
volume = {185},
pages = {20:1--20:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2021.20},
doi = {10.4230/LIPICS.ITCS.2021.20},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/0001DLSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigecom/ChenKK21,
author = {Xi Chen and
Christian Kroer and
Rachitesh Kumar},
editor = {P{\'{e}}ter Bir{\'{o}} and
Shuchi Chawla and
Federico Echenique},
title = {The Complexity of Pacing for Second-Price Auctions},
booktitle = {{EC} '21: The 22nd {ACM} Conference on Economics and Computation,
Budapest, Hungary, July 18-23, 2021},
pages = {318},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3465456.3467578},
doi = {10.1145/3465456.3467578},
timestamp = {Fri, 09 Feb 2024 20:36:00 +0100},
biburl = {https://dblp.org/rec/conf/sigecom/ChenKK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDLSS21,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
editor = {D{\'{a}}niel Marx},
title = {Polynomial-time trace reconstruction in the smoothed complexity model},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {54--73},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.5},
doi = {10.1137/1.9781611976465.5},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChenDLSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/CanonneCKLW21,
author = {Cl{\'{e}}ment L. Canonne and
Xi Chen and
Gautam Kamath and
Amit Levi and
Erik Waingarten},
editor = {D{\'{a}}niel Marx},
title = {Random Restrictions of High Dimensional Distributions and Uniformity
Testing with Subcube Conditioning},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {321--336},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.21},
doi = {10.1137/1.9781611976465.21},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/CanonneCKLW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wine/ChenKK21,
author = {Xi Chen and
Christian Kroer and
Rachitesh Kumar},
editor = {Michal Feldman and
Hu Fu and
Inbal Talgam{-}Cohen},
title = {Throttling Equilibria in Auction Markets},
booktitle = {Web and Internet Economics - 17th International Conference, {WINE}
2021, Potsdam, Germany, December 14-17, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13112},
pages = {551},
publisher = {Springer},
year = {2021},
url = {https://link.springer.com/content/pdf/bbm\%3A978-3-030-94676-0\%2F1},
timestamp = {Mon, 30 Oct 2023 12:09:00 +0100},
biburl = {https://dblp.org/rec/conf/wine/ChenKK21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2103-13969,
author = {Xi Chen and
Christian Kroer and
Rachitesh Kumar},
title = {The Complexity of Pacing for Second-Price Auctions},
journal = {CoRR},
volume = {abs/2103.13969},
year = {2021},
url = {https://arxiv.org/abs/2103.13969},
eprinttype = {arXiv},
eprint = {2103.13969},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2103-13969.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-05746,
author = {Thomas Chen and
Xi Chen and
Binghui Peng and
Mihalis Yannakakis},
title = {Computational Hardness of the Hylland-Zeckhauser Scheme},
journal = {CoRR},
volume = {abs/2107.05746},
year = {2021},
url = {https://arxiv.org/abs/2107.05746},
eprinttype = {arXiv},
eprint = {2107.05746},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-05746.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-10923,
author = {Xi Chen and
Christian Kroer and
Rachitesh Kumar},
title = {Throttling Equilibria in Auction Markets},
journal = {CoRR},
volume = {abs/2107.10923},
year = {2021},
url = {https://arxiv.org/abs/2107.10923},
eprinttype = {arXiv},
eprint = {2107.10923},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-10923.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-11530,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Near-Optimal Average-Case Approximate Trace Reconstruction from Few
Traces},
journal = {CoRR},
volume = {abs/2107.11530},
year = {2021},
url = {https://arxiv.org/abs/2107.11530},
eprinttype = {arXiv},
eprint = {2107.11530},
timestamp = {Thu, 29 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-11530.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-14607,
author = {Xi Chen and
Yaonan Jin and
Tim Randolph and
Rocco A. Servedio},
title = {Average-Case Subset Balancing Problems},
journal = {CoRR},
volume = {abs/2110.14607},
year = {2021},
url = {https://arxiv.org/abs/2110.14607},
eprinttype = {arXiv},
eprint = {2110.14607},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-14607.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2111-03198,
author = {Xi Chen and
Binghui Peng},
title = {On the Complexity of Dynamic Submodular Maximization},
journal = {CoRR},
volume = {abs/2111.03198},
year = {2021},
url = {https://arxiv.org/abs/2111.03198},
eprinttype = {arXiv},
eprint = {2111.03198},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2111-03198.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2111-03528,
author = {Xi Chen and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
title = {New Streaming Algorithms for High Dimensional {EMD} and {MST}},
journal = {CoRR},
volume = {abs/2111.03528},
year = {2021},
url = {https://arxiv.org/abs/2111.03528},
eprinttype = {arXiv},
eprint = {2111.03528},
timestamp = {Fri, 25 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2111-03528.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ChenP20,
author = {Xi Chen and
Binghui Peng},
editor = {Hugo Larochelle and
Marc'Aurelio Ranzato and
Raia Hadsell and
Maria{-}Florina Balcan and
Hsuan{-}Tien Lin},
title = {Hedging in games: Faster convergence of external and swap regrets},
booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference
on Neural Information Processing Systems 2020, NeurIPS 2020, December
6-12, 2020, virtual},
year = {2020},
url = {https://proceedings.neurips.cc/paper/2020/hash/db346ccb62d491029b590bbbf0f5c412-Abstract.html},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/nips/ChenP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/0001LW20,
author = {Xi Chen and
Amit Levi and
Erik Waingarten},
editor = {Shuchi Chawla},
title = {Nearly optimal edge estimation with independent set queries},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {2916--2935},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.177},
doi = {10.1137/1.9781611975994.177},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/0001LW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenRSS20,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
editor = {Shuchi Chawla},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {2936--2952},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.178},
doi = {10.1137/1.9781611975994.178},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenRSS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenGVYZ20,
author = {Xi Chen and
Chenghao Guo and
Emmanouil V. Vlatakis{-}Gkaragkounis and
Mihalis Yannakakis and
Xinzhi Zhang},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Smoothed complexity of local max-cut and binary max-CSP},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {1052--1065},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384325},
doi = {10.1145/3357713.3384325},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenGVYZ20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2004-12496,
author = {Xi Chen and
Rajesh Jayaram and
Amit Levi and
Erik Waingarten},
title = {Learning and Testing Junta Distributions with Subcube Conditioning},
journal = {CoRR},
volume = {abs/2004.12496},
year = {2020},
url = {https://arxiv.org/abs/2004.12496},
eprinttype = {arXiv},
eprint = {2004.12496},
timestamp = {Wed, 29 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2004-12496.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2006-04953,
author = {Xi Chen and
Binghui Peng},
title = {Hedging in games: Faster convergence of external and swap regrets},
journal = {CoRR},
volume = {abs/2006.04953},
year = {2020},
url = {https://arxiv.org/abs/2006.04953},
eprinttype = {arXiv},
eprint = {2006.04953},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2006-04953.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2008-12386,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Polynomial-time trace reconstruction in the smoothed complexity model},
journal = {CoRR},
volume = {abs/2008.12386},
year = {2020},
url = {https://arxiv.org/abs/2008.12386},
eprinttype = {arXiv},
eprint = {2008.12386},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2008-12386.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2012-02844,
author = {Xi Chen and
Anindya De and
Chin Ho Lee and
Rocco A. Servedio and
Sandip Sinha},
title = {Polynomial-time trace reconstruction in the low deletion rate regime},
journal = {CoRR},
volume = {abs/2012.02844},
year = {2020},
url = {https://arxiv.org/abs/2012.02844},
eprinttype = {arXiv},
eprint = {2012.02844},
timestamp = {Thu, 04 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2012-02844.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiC19,
author = {Jin{-}Yi Cai and
Xi Chen},
title = {A decidable dichotomy theorem on directed graph homomorphisms with
non-negative weights},
journal = {Comput. Complex.},
volume = {28},
number = {3},
pages = {345--408},
year = {2019},
url = {https://doi.org/10.1007/s00037-019-00184-5},
doi = {10.1007/S00037-019-00184-5},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/CaiC19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/LiuCSSX19,
author = {Zhengyang Liu and
Xi Chen and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
title = {Distribution-free Junta Testing},
journal = {{ACM} Trans. Algorithms},
volume = {15},
number = {1},
pages = {1:1--1:23},
year = {2019},
url = {https://doi.org/10.1145/3264434},
doi = {10.1145/3264434},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/LiuCSSX19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aft/ChenPR19,
author = {Xi Chen and
Christos H. Papadimitriou and
Tim Roughgarden},
title = {An Axiomatic Approach to Block Rewards},
booktitle = {Proceedings of the 1st {ACM} Conference on Advances in Financial Technologies,
{AFT} 2019, Zurich, Switzerland, October 21-23, 2019},
pages = {124--131},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3318041.3355470},
doi = {10.1145/3318041.3355470},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/aft/ChenPR19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Ban0SS19,
author = {Frank Ban and
Xi Chen and
Rocco A. Servedio and
Sandip Sinha},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Efficient Average-Case Population Recovery in the Presence of Insertions
and Deletions},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2019, September 20-22, 2019, Massachusetts
Institute of Technology, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {145},
pages = {44:1--44:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.44},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.44},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Ban0SS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Ban0FSS19,
author = {Frank Ban and
Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Sandip Sinha},
editor = {David Zuckerman},
title = {Beyond Trace Reconstruction: Population Recovery from the Deletion
Channel},
booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2019, Baltimore, Maryland, USA, November 9-12, 2019},
pages = {745--768},
publisher = {{IEEE} Computer Society},
year = {2019},
url = {https://doi.org/10.1109/FOCS.2019.00050},
doi = {10.1109/FOCS.2019.00050},
timestamp = {Tue, 07 Jan 2020 13:25:31 +0100},
biburl = {https://dblp.org/rec/conf/focs/Ban0FSS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenW19,
author = {Xi Chen and
Erik Waingarten},
editor = {Moses Charikar and
Edith Cohen},
title = {Testing unateness nearly optimally},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {547--558},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316351},
doi = {10.1145/3313276.3316351},
timestamp = {Fri, 31 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChenW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-05309,
author = {Xi Chen and
Erik Waingarten},
title = {Testing Unateness Nearly Optimally},
journal = {CoRR},
volume = {abs/1904.05309},
year = {2019},
url = {http://arxiv.org/abs/1904.05309},
eprinttype = {arXiv},
eprint = {1904.05309},
timestamp = {Thu, 25 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-05309.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-05532,
author = {Frank Ban and
Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Sandip Sinha},
title = {Beyond trace reconstruction: Population recovery from the deletion
channel},
journal = {CoRR},
volume = {abs/1904.05532},
year = {2019},
url = {http://arxiv.org/abs/1904.05532},
eprinttype = {arXiv},
eprint = {1904.05532},
timestamp = {Sat, 23 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-05532.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-04381,
author = {Xi Chen and
Amit Levi and
Erik Waingarten},
title = {Nearly optimal edge estimation with independent set queries},
journal = {CoRR},
volume = {abs/1907.04381},
year = {2019},
url = {http://arxiv.org/abs/1907.04381},
eprinttype = {arXiv},
eprint = {1907.04381},
timestamp = {Fri, 31 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-04381.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-05964,
author = {Frank Ban and
Xi Chen and
Rocco A. Servedio and
Sandip Sinha},
title = {Efficient average-case population recovery in the presence of insertions
and deletions},
journal = {CoRR},
volume = {abs/1907.05964},
year = {2019},
url = {http://arxiv.org/abs/1907.05964},
eprinttype = {arXiv},
eprint = {1907.05964},
timestamp = {Tue, 07 Jan 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-05964.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-12106,
author = {Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun},
title = {A Lower Bound on Cycle-Finding in Sparse Digraphs},
journal = {CoRR},
volume = {abs/1907.12106},
year = {2019},
url = {http://arxiv.org/abs/1907.12106},
eprinttype = {arXiv},
eprint = {1907.12106},
timestamp = {Tue, 22 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-12106.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1909-10645,
author = {Xi Chen and
Christos H. Papadimitriou and
Tim Roughgarden},
title = {An Axiomatic Approach to Block Rewards},
journal = {CoRR},
volume = {abs/1909.10645},
year = {2019},
url = {http://arxiv.org/abs/1909.10645},
eprinttype = {arXiv},
eprint = {1909.10645},
timestamp = {Thu, 13 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1909-10645.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-07357,
author = {Cl{\'{e}}ment L. Canonne and
Xi Chen and
Gautam Kamath and
Amit Levi and
Erik Waingarten},
title = {Random Restrictions of High-Dimensional Distributions and Uniformity
Testing with Subcube Conditioning},
journal = {CoRR},
volume = {abs/1911.07357},
year = {2019},
url = {http://arxiv.org/abs/1911.07357},
eprinttype = {arXiv},
eprint = {1911.07357},
timestamp = {Mon, 09 Dec 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-07357.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-10381,
author = {Xi Chen and
Chenghao Guo and
Emmanouil V. Vlatakis{-}Gkaragkounis and
Mihalis Yannakakis and
Xinzhi Zhang},
title = {Smoothed complexity of local Max-Cut and binary Max-CSP},
journal = {CoRR},
volume = {abs/1911.10381},
year = {2019},
url = {http://arxiv.org/abs/1911.10381},
eprinttype = {arXiv},
eprint = {1911.10381},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-10381.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CanonneCKLW19,
author = {Cl{\'{e}}ment L. Canonne and
Xi Chen and
Gautam Kamath and
Amit Levi and
Erik Waingarten},
title = {Random Restrictions of High-Dimensional Distributions and Uniformity
Testing with Subcube Conditioning},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-165}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/165},
eprinttype = {ECCC},
eprint = {TR19-165},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CanonneCKLW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/geb/ChenDPSY18,
author = {Xi Chen and
Ilias Diakonikolas and
Dimitris Paparas and
Xiaorui Sun and
Mihalis Yannakakis},
title = {The complexity of optimal multidimensional pricing for a unit-demand
buyer},
journal = {Games Econ. Behav.},
volume = {110},
pages = {139--164},
year = {2018},
url = {https://doi.org/10.1016/j.geb.2018.03.016},
doi = {10.1016/J.GEB.2018.03.016},
timestamp = {Sat, 22 Feb 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/geb/ChenDPSY18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChenSTWX18,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the Query Complexity of Non-adaptive Junta Testing},
journal = {J. {ACM}},
volume = {65},
number = {6},
pages = {40:1--40:18},
year = {2018},
url = {https://doi.org/10.1145/3213772},
doi = {10.1145/3213772},
timestamp = {Thu, 09 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/ChenSTWX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenMPY18,
author = {Xi Chen and
George Matikas and
Dimitris Paparas and
Mihalis Yannakakis},
editor = {Artur Czumaj},
title = {On the Complexity of Simple and Optimal Deterministic Mechanisms for
an Additive Buyer},
booktitle = {Proceedings of the Twenty-Ninth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2018, New Orleans, LA, USA, January 7-10, 2018},
pages = {2036--2049},
publisher = {{SIAM}},
year = {2018},
url = {https://doi.org/10.1137/1.9781611975031.133},
doi = {10.1137/1.9781611975031.133},
timestamp = {Tue, 02 Feb 2021 17:07:58 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenMPY18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LiuCSSX18,
author = {Zhengyang Liu and
Xi Chen and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Distribution-free junta testing},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {749--759},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188842},
doi = {10.1145/3188745.3188842},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/LiuCSSX18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1802-04859,
author = {Xi Chen and
Zhengyang Liu and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie},
title = {Distribution-free Junta Testing},
journal = {CoRR},
volume = {abs/1802.04859},
year = {2018},
url = {http://arxiv.org/abs/1802.04859},
eprinttype = {arXiv},
eprint = {1802.04859},
timestamp = {Fri, 17 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1802-04859.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/CaiC17,
author = {Jin{-}Yi Cai and
Xi Chen},
title = {Complexity of Counting {CSP} with Complex Weights},
journal = {J. {ACM}},
volume = {64},
number = {3},
pages = {19:1--19:39},
year = {2017},
url = {https://doi.org/10.1145/2822891},
doi = {10.1145/2822891},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/CaiC17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChenPY17,
author = {Xi Chen and
Dimitris Paparas and
Mihalis Yannakakis},
title = {The Complexity of Non-Monotone Markets},
journal = {J. {ACM}},
volume = {64},
number = {3},
pages = {20:1--20:56},
year = {2017},
url = {https://doi.org/10.1145/3064810},
doi = {10.1145/3064810},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/ChenPY17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001FSS17,
author = {Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Timothy Sun},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Williamson and
Santosh S. Vempala},
title = {Sample-Based High-Dimensional Convexity Testing},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2017, August 16-18, 2017, Berkeley,
CA, {USA}},
series = {LIPIcs},
volume = {81},
pages = {37:1--37:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.37},
doi = {10.4230/LIPICS.APPROX-RANDOM.2017.37},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001FSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/0001STW17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
David Williamson and
Santosh S. Vempala},
title = {Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2017, August 16-18, 2017, Berkeley,
CA, {USA}},
series = {LIPIcs},
volume = {81},
pages = {38:1--38:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.38},
doi = {10.4230/LIPICS.APPROX-RANDOM.2017.38},
timestamp = {Thu, 23 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/0001STW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
editor = {Ryan O'Donnell},
title = {Settling the Query Complexity of Non-Adaptive Junta Testing},
booktitle = {32nd Computational Complexity Conference, {CCC} 2017, July 6-9, 2017,
Riga, Latvia},
series = {LIPIcs},
volume = {79},
pages = {26:1--26:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.CCC.2017.26},
doi = {10.4230/LIPICS.CCC.2017.26},
timestamp = {Thu, 02 Feb 2023 13:27:05 +0100},
biburl = {https://dblp.org/rec/conf/coco/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenWX17,
author = {Xi Chen and
Erik Waingarten and
Jinyu Xie},
editor = {Chris Umans},
title = {Boolean Unateness Testing with {\~{O}}(n\({}^{\mbox{3/4}}\)) Adaptive
Queries},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {868--879},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.85},
doi = {10.1109/FOCS.2017.85},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ChenCT17,
author = {Xi Chen and
Yu Cheng and
Bo Tang},
editor = {Christos H. Papadimitriou},
title = {Well-Supported vs. Approximate Nash Equilibria: Query Complexity of
Large Games},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {57:1--57:9},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.57},
doi = {10.4230/LIPICS.ITCS.2017.57},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ChenCT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenWX17,
author = {Xi Chen and
Erik Waingarten and
Jinyu Xie},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Beyond Talagrand functions: new lower bounds for testing monotonicity
and unateness},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {523--536},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055461},
doi = {10.1145/3055399.3055461},
timestamp = {Sun, 02 Jun 2019 21:10:31 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenOS17,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio},
editor = {Hamed Hatami and
Pierre McKenzie and
Valerie King},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
pages = {1232--1245},
publisher = {{ACM}},
year = {2017},
url = {https://doi.org/10.1145/3055399.3055425},
doi = {10.1145/3055399.3055425},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenOS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenWX17,
author = {Xi Chen and
Erik Waingarten and
Jinyu Xie},
title = {Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity
and Unateness},
journal = {CoRR},
volume = {abs/1702.06997},
year = {2017},
url = {http://arxiv.org/abs/1702.06997},
eprinttype = {arXiv},
eprint = {1702.06997},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenMPY17,
author = {Xi Chen and
George Matikas and
Dimitris Paparas and
Mihalis Yannakakis},
title = {On the Complexity of Bundle-Pricing and Simple Mechanisms},
journal = {CoRR},
volume = {abs/1702.07032},
year = {2017},
url = {http://arxiv.org/abs/1702.07032},
eprinttype = {arXiv},
eprint = {1702.07032},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenMPY17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the query complexity of non-adaptive junta testing},
journal = {CoRR},
volume = {abs/1704.06314},
year = {2017},
url = {http://arxiv.org/abs/1704.06314},
eprinttype = {arXiv},
eprint = {1704.06314},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/0001STW17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten},
title = {Adaptivity is exponentially powerful for testing monotonicity of halfspaces},
journal = {CoRR},
volume = {abs/1706.05556},
year = {2017},
url = {http://arxiv.org/abs/1706.05556},
eprinttype = {arXiv},
eprint = {1706.05556},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/0001STW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenFSS17,
author = {Xi Chen and
Adam Freilich and
Rocco A. Servedio and
Timothy Sun},
title = {Sample-based high-dimensional convexity testing},
journal = {CoRR},
volume = {abs/1706.09362},
year = {2017},
url = {http://arxiv.org/abs/1706.09362},
eprinttype = {arXiv},
eprint = {1706.09362},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenFSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1708-05786,
author = {Xi Chen and
Erik Waingarten and
Jinyu Xie},
title = {Boolean Unateness Testing with O{\~}(n\({}^{\mbox{3/4}}\)) Adaptive
Queries},
journal = {CoRR},
volume = {abs/1708.05786},
year = {2017},
url = {http://arxiv.org/abs/1708.05786},
eprinttype = {arXiv},
eprint = {1708.05786},
timestamp = {Wed, 19 Dec 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1708-05786.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenSTWX17,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan and
Erik Waingarten and
Jinyu Xie},
title = {Settling the query complexity of non-adaptive junta testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-068}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/068},
eprinttype = {ECCC},
eprint = {TR17-068},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenSTWX17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiCL16,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Nonnegative Weighted {\#}CSP: An Effective Complexity Dichotomy},
journal = {{SIAM} J. Comput.},
volume = {45},
number = {6},
pages = {2177--2198},
year = {2016},
url = {https://doi.org/10.1137/15M1032314},
doi = {10.1137/15M1032314},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiCL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ChenCCT16,
author = {Xi Chen and
Yu Cheng and
Bo Tang},
editor = {Daniel D. Lee and
Masashi Sugiyama and
Ulrike von Luxburg and
Isabelle Guyon and
Roman Garnett},
title = {On the Recursive Teaching Dimension of {VC} Classes},
booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference
on Neural Information Processing Systems 2016, December 5-10, 2016,
Barcelona, Spain},
pages = {2164--2171},
year = {2016},
url = {https://proceedings.neurips.cc/paper/2016/hash/69a5b5995110b36a9a347898d97a610e-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/ChenCCT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenX16,
author = {Xi Chen and
Jinyu Xie},
editor = {Robert Krauthgamer},
title = {Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {54--71},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch5},
doi = {10.1137/1.9781611974331.CH5},
timestamp = {Tue, 02 Feb 2021 17:07:56 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenX16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenOST16,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Near-optimal small-depth lower bounds for small distance connectivity},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {612--625},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897534},
doi = {10.1145/2897518.2897534},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenOST16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/CaiCL16,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Complexity Dichotomies for Counting Graph Homomorphisms},
booktitle = {Encyclopedia of Algorithms},
pages = {366--369},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_747},
doi = {10.1007/978-1-4939-2864-4\_747},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/CaiCL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/ChenD16,
author = {Xi Chen and
Xiaotie Deng},
title = {Non-approximability of Bimatrix Nash Equilibria},
booktitle = {Encyclopedia of Algorithms},
pages = {1412--1414},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_258},
doi = {10.1007/978-1-4939-2864-4\_258},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/ChenD16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenCT16,
author = {Xi Chen and
Yu Cheng and
Bo Tang},
title = {A Note on Teaching for {VC} Classes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-065}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/065},
eprinttype = {ECCC},
eprint = {TR16-065},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenCT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenDOPSY15,
author = {Xi Chen and
Ilias Diakonikolas and
Anthi Orfanou and
Dimitris Paparas and
Xiaorui Sun and
Mihalis Yannakakis},
editor = {Venkatesan Guruswami},
title = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {1464--1479},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.93},
doi = {10.1109/FOCS.2015.93},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenDOPSY15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenDO15,
author = {Xi Chen and
David Durfee and
Anthi Orfanou},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {On the Complexity of Nash Equilibria in Anonymous Games},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {381--390},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746571},
doi = {10.1145/2746539.2746571},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenDO15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenDST15,
author = {Xi Chen and
Anindya De and
Rocco A. Servedio and
Li{-}Yang Tan},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Boolean Function Monotonicity Testing Requires (Almost) n\({}^{\mbox{1/2}}\)
Non-adaptive Queries},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {519--528},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746570},
doi = {10.1145/2746539.2746570},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChenDST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenOS15,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
journal = {CoRR},
volume = {abs/1508.03061},
year = {2015},
url = {http://arxiv.org/abs/1508.03061},
eprinttype = {arXiv},
eprint = {1508.03061},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenOS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenOST15,
author = {Xi Chen and
Igor C. Oliveira and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Near-optimal small-depth lower bounds for small distance connectivity},
journal = {CoRR},
volume = {abs/1509.07476},
year = {2015},
url = {http://arxiv.org/abs/1509.07476},
eprinttype = {arXiv},
eprint = {1509.07476},
timestamp = {Tue, 30 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenOST15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenCT15,
author = {Xi Chen and
Yu Cheng and
Bo Tang},
title = {Well-Supported versus Approximate Nash Equilibria: Query Complexity
of Large Games},
journal = {CoRR},
volume = {abs/1511.00785},
year = {2015},
url = {http://arxiv.org/abs/1511.00785},
eprinttype = {arXiv},
eprint = {1511.00785},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenCT15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenX15a,
author = {Xi Chen and
Jinyu Xie},
title = {Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions},
journal = {CoRR},
volume = {abs/1511.03333},
year = {2015},
url = {http://arxiv.org/abs/1511.03333},
eprinttype = {arXiv},
eprint = {1511.03333},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenX15a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenOS15,
author = {Xi Chen and
Igor Carboni Oliveira and
Rocco A. Servedio},
title = {Addition is exponentially harder than counting for shallow monotone
circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-123}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/123},
eprinttype = {ECCC},
eprint = {TR15-123},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenOS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenST14,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {New Algorithms and Lower Bounds for Monotonicity Testing},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {286--295},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.38},
doi = {10.1109/FOCS.2014.38},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenDPSY14,
author = {Xi Chen and
Ilias Diakonikolas and
Dimitris Paparas and
Xiaorui Sun and
Mihalis Yannakakis},
editor = {Chandra Chekuri},
title = {The Complexity of Optimal Multidimensional Pricing},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1319--1328},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.97},
doi = {10.1137/1.9781611973402.97},
timestamp = {Tue, 02 Feb 2021 17:07:40 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenDPSY14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenST14,
author = {Xi Chen and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {New algorithms and lower bounds for monotonicity testing},
journal = {CoRR},
volume = {abs/1412.5655},
year = {2014},
url = {http://arxiv.org/abs/1412.5655},
eprinttype = {arXiv},
eprint = {1412.5655},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenDST14,
author = {Xi Chen and
Anindya De and
Rocco A. Servedio and
Li{-}Yang Tan},
title = {Boolean function monotonicity testing requires (almost) n\({}^{\mbox{1/2}}\)
non-adaptive queries},
journal = {CoRR},
volume = {abs/1412.5657},
year = {2014},
url = {http://arxiv.org/abs/1412.5657},
eprinttype = {arXiv},
eprint = {1412.5657},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenDST14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenDO14,
author = {Xi Chen and
David Durfee and
Anthi Orfanou},
title = {On the Complexity of Nash Equilibria in Anonymous Games},
journal = {CoRR},
volume = {abs/1412.5681},
year = {2014},
url = {http://arxiv.org/abs/1412.5681},
eprinttype = {arXiv},
eprint = {1412.5681},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenDO14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/CaiCL13,
author = {Jin{-}Yi Cai and
Xi Chen and
Pinyan Lu},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {3},
pages = {924--1029},
year = {2013},
url = {https://doi.org/10.1137/110840194},
doi = {10.1137/110840194},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/CaiCL13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BarakBCR13,
author = {Boaz Barak and
Mark Braverman and
Xi Chen and
Anup Rao},
title = {How to Compress Interactive Communication},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {3},
pages = {1327--1363},
year = {2013},
url = {https://doi.org/10.1137/100811969},
doi = {10.1137/100811969},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BarakBCR13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BabaiCSTW13,
author = {L{\'{a}}szl{\'{o}} Babai and
Xi Chen and
Xiaorui Sun and
Shang{-}Hua Teng and
John Wilmes},
title = {Faster Canonical Forms for Strongly Regular Graphs},
booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2013, 26-29 October, 2013, Berkeley, CA, {USA}},
pages = {157--166},
publisher = {{IEEE} Computer Society},
year = {2013},
url = {https://doi.org/10.1109/FOCS.2013.25},
doi = {10.1109/FOCS.2013.25},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BabaiCSTW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenPY13,
author = {Xi Chen and
Dimitris Paparas and
Mihalis Yannakakis},
editor = {Dan Boneh and
Tim Roughgarden and
Joan Feigenbaum},
title = {The complexity of non-monotone markets},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
USA, June 1-4, 2013},
pages = {181--190},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2488608.2488632},
doi = {10.1145/2488608.2488632},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenPY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenST13,
author = {Xi Chen and
Xiaorui Sun and
Shang{-}Hua Teng},
editor = {Dan Boneh and
Tim Roughgarden and
Joan Feigenbaum},
title = {Multi-stage design for quasipolynomial-time isomorphism testing of
steiner 2-systems},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
USA, June 1-4, 2013},
pages = {271--280},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2488608.2488643},
doi = {10.1145/2488608.2488643},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenST13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChenDPSY13,
author = {Xi Chen and
Ilias Diakonikolas and
Dimitris Paparas and
Xiaorui Sun and
Mihalis Yannakakis},
title = {The Complexity of Optimal Multidimensional Pricing},
journal = {CoRR},
volume = {abs/1311.2138},
year = {2013},
url = {http://arxiv.org/abs/1311.2138},
eprinttype = {arXiv},
eprint = {1311.2138},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChenDPSY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoa/CaiCGL12,
author = {Jin{-}Yi Cai and
Xi Chen and
Heng Guo and
Pinyan Lu},
editor = {Guohui Lin},
title = {Inapproximability after Uniqueness Phase Transition in Two-Spin Systems},
booktitle = {Combinatorial Optimization and Applications - 6th International Conference,
{COCOA} 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7402},
pages = {336--347},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31770-5\_30},
doi = {10.1007/978-3-642-31770-5\_30},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoa/CaiCGL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiC12,
author = {Jin{-}Yi Cai and
Xi Chen},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {Complexity of counting {CSP} with complex weights},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {909--920},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2214059},
doi = {10.1145/2213977.2214059},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiC12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1205-2934,
author = {Jin{-}Yi Cai and
Xi Chen and
Heng Guo and
Pinyan Lu},
title = {Inapproximability After Uniqueness Phase Transition in Two-Spin Systems},
journal = {CoRR},
volume = {abs/1205.2934},
year = {2012},
url = {http://arxiv.org/abs/1205.2934},
eprinttype = {arXiv},
eprint = {1205.2934},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1205-2934.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1211-4918,
author = {Xi Chen and
Dimitris Paparas and
Mihalis Yannakakis},
title = {The Complexity of Non-Monotone Markets},
journal = {CoRR},
volume = {abs/1211.4918},
year = {2012},
url = {http://arxiv.org/abs/1211.4918},
eprinttype = {arXiv},
eprint = {1211.4918},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1211-4918.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/ChenDL11,
author = {Xi Chen and
Xiaotie Deng and
Becky Jie Liu},
title = {On Incentive Compatible Competitive Selection Protocols},
journal = {Algorithmica},
volume = {61},
number = {2},
pages = {447--462},
year = {2011},
url = {https://doi.org/10.1007/s00453-010-9395-z},
doi = {10.1007/S00453-010-9395-Z},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/ChenDL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/fttcs/ChenKW11,
author = {Xi Chen and
Neeraj Kayal and
Avi Wigderson},
title = {Partial Derivatives in Arithmetic Complexity and Beyond},
journal = {Found. Trends Theor. Comput. Sci.},
volume = {6},
number = {1-2},
pages = {1--138},
year = {2011},
url = {https://doi.org/10.1561/0400000043},
doi = {10.1561/0400000043},
timestamp = {Thu, 20 Aug 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/fttcs/ChenKW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/Chen11a,
author = {Xi Chen},
title = {Guest column: complexity dichotomies of counting problems},
journal = {{SIGACT} News},
volume = {42},
number = {4},
pages = {54--76},
year = {2011},
url = {https://doi.org/10.1145/2078162.2078177},
doi = {10.1145/2078162.2078177},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/sigact/Chen11a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/CaiCL11,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Non-negatively Weighted {\#}CSP: An Effective Complexity Dichotomy},
booktitle = {Proceedings of the 26th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2011, San Jose, California, USA, June 8-10, 2011},
pages = {45--54},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/CCC.2011.32},
doi = {10.1109/CCC.2011.32},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/CaiCL11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ChenT11,
author = {Xi Chen and
Shang{-}Hua Teng},
editor = {Bernard Chazelle},
title = {A Complexity View of Markets with Social Influence},
booktitle = {Innovations in Computer Science - {ICS} 2011, Tsinghua University,
Beijing, China, January 7-9, 2011. Proceedings},
pages = {141--154},
publisher = {Tsinghua University Press},
year = {2011},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/16.html},
timestamp = {Mon, 23 Mar 2020 08:26:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ChenT11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1111-2384,
author = {Jin{-}yi Cai and
Xi Chen},
title = {Complexity of Counting {CSP} with Complex Weights},
journal = {CoRR},
volume = {abs/1111.2384},
year = {2011},
url = {http://arxiv.org/abs/1111.2384},
eprinttype = {arXiv},
eprint = {1111.2384},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1111-2384.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/ChenST10,
author = {Xi Chen and
Xiaoming Sun and
Shang{-}Hua Teng},
title = {Quantum Separation of Local Search and Fixed Point Computation},
journal = {Algorithmica},
volume = {56},
number = {3},
pages = {364--382},
year = {2010},
url = {https://doi.org/10.1007/s00453-009-9289-0},
doi = {10.1007/S00453-009-9289-0},
timestamp = {Wed, 26 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/ChenST10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/CaiCL10,
author = {Jin{-}yi Cai and
Xi Chen and
Dong Li},
title = {Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic},
journal = {Comput. Complex.},
volume = {19},
number = {1},
pages = {37--56},
year = {2010},
url = {https://doi.org/10.1007/s00037-009-0284-2},
doi = {10.1007/S00037-009-0284-2},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/CaiCL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/bqgt/ChenDDT10,
author = {Xi Chen and
Decheng Dai and
Ye Du and
Shang{-}Hua Teng},
editor = {Moshe Dror and
Greys Sosic},
title = {On the complexity of equilibria in markets with additively separable
utilities},
booktitle = {Proceedings of the Behavioral and Quantitative Game Theory - Conference
on Future Directions, {BQGT} '10, Newport Beach, California, USA,
May 14-16, 2010},
pages = {61:1},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1807406.1807467},
doi = {10.1145/1807406.1807467},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/bqgt/ChenDDT10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/faw/CaiCLL10,
author = {Jin{-}yi Cai and
Xi Chen and
Richard J. Lipton and
Pinyan Lu},
editor = {Der{-}Tsai Lee and
Danny Z. Chen and
Shi Ying},
title = {On Tractable Exponential Sums},
booktitle = {Frontiers in Algorithmics, 4th International Workshop, {FAW} 2010,
Wuhan, China, August 11-13, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6213},
pages = {148--159},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14553-7\_16},
doi = {10.1007/978-3-642-14553-7\_16},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/faw/CaiCLL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/CaiC10,
author = {Jin{-}yi Cai and
Xi Chen},
title = {A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with
Non-negative Weights},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {437--446},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.49},
doi = {10.1109/FOCS.2010.49},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/CaiC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/CaiCL10,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
editor = {Samson Abramsky and
Cyril Gavoille and
Claude Kirchner and
Friedhelm Meyer auf der Heide and
Paul G. Spirakis},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
booktitle = {Automata, Languages and Programming, 37th International Colloquium,
{ICALP} 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part
{I}},
series = {Lecture Notes in Computer Science},
volume = {6198},
pages = {275--286},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14165-2\_24},
doi = {10.1007/978-3-642-14165-2\_24},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/CaiCL10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BarakBCR10,
author = {Boaz Barak and
Mark Braverman and
Xi Chen and
Anup Rao},
editor = {Leonard J. Schulman},
title = {How to compress interactive communication},
booktitle = {Proceedings of the 42nd {ACM} Symposium on Theory of Computing, {STOC}
2010, Cambridge, Massachusetts, USA, 5-8 June 2010},
pages = {67--76},
publisher = {{ACM}},
year = {2010},
url = {https://doi.org/10.1145/1806689.1806701},
doi = {10.1145/1806689.1806701},
timestamp = {Sat, 05 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/BarakBCR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1005-2632,
author = {Jin{-}yi Cai and
Xi Chen and
Richard J. Lipton and
Pinyan Lu},
title = {On Tractable Exponential Sums},
journal = {CoRR},
volume = {abs/1005.2632},
year = {2010},
url = {http://arxiv.org/abs/1005.2632},
eprinttype = {arXiv},
eprint = {1005.2632},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1005-2632.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1008-0915,
author = {Jin{-}yi Cai and
Xi Chen},
title = {A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with
Non-negative Weights},
journal = {CoRR},
volume = {abs/1008.0915},
year = {2010},
url = {http://arxiv.org/abs/1008.0915},
eprinttype = {arXiv},
eprint = {1008.0915},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1008-0915.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1009-0309,
author = {Xi Chen and
Shang{-}Hua Teng},
title = {A Complexity View of Markets with Social Influence},
journal = {CoRR},
volume = {abs/1009.0309},
year = {2010},
url = {http://arxiv.org/abs/1009.0309},
eprinttype = {arXiv},
eprint = {1009.0309},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1009-0309.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1012-5659,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Non-negative Weighted {\#}CSPs: An Effective Complexity Dichotomy},
journal = {CoRR},
volume = {abs/1012.5659},
year = {2010},
url = {http://arxiv.org/abs/1012.5659},
eprinttype = {arXiv},
eprint = {1012.5659},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1012-5659.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/ChenD09,
author = {Xi Chen and
Xiaotie Deng},
title = {A Simplicial Approach for Discrete Fixed Point Theorems},
journal = {Algorithmica},
volume = {53},
number = {2},
pages = {250--262},
year = {2009},
url = {https://doi.org/10.1007/s00453-008-9183-1},
doi = {10.1007/S00453-008-9183-1},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/algorithmica/ChenD09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChenDT09,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
title = {Settling the complexity of computing two-player Nash equilibria},
journal = {J. {ACM}},
volume = {56},
number = {3},
pages = {14:1--14:57},
year = {2009},
url = {https://doi.org/10.1145/1516512.1516516},
doi = {10.1145/1516512.1516516},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/ChenDT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/ChenHT09,
author = {Xi Chen and
Li{-}Sha Huang and
Shang{-}Hua Teng},
title = {Market equilibria with hybrid linear-Leontief utilities},
journal = {Theor. Comput. Sci.},
volume = {410},
number = {17},
pages = {1573--1580},
year = {2009},
url = {https://doi.org/10.1016/j.tcs.2008.12.030},
doi = {10.1016/J.TCS.2008.12.030},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/ChenHT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/ChenD09,
author = {Xi Chen and
Xiaotie Deng},
title = {On the complexity of 2D discrete fixed point problem},
journal = {Theor. Comput. Sci.},
volume = {410},
number = {44},
pages = {4448--4456},
year = {2009},
url = {https://doi.org/10.1016/j.tcs.2009.07.052},
doi = {10.1016/J.TCS.2009.07.052},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/ChenD09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenDDT09,
author = {Xi Chen and
Decheng Dai and
Ye Du and
Shang{-}Hua Teng},
title = {Settling the Complexity of Arrow-Debreu Equilibria in Markets with
Additively Separable Utilities},
booktitle = {50th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2009, October 25-27, 2009, Atlanta, Georgia, {USA}},
pages = {273--282},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/FOCS.2009.29},
doi = {10.1109/FOCS.2009.29},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenDDT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/ChenT09,
author = {Xi Chen and
Shang{-}Hua Teng},
editor = {Yingfei Dong and
Ding{-}Zhu Du and
Oscar H. Ibarra},
title = {Spending Is Not Easier Than Trading: On the Computational Equivalence
of Fisher and Arrow-Debreu Equilibria},
booktitle = {Algorithms and Computation, 20th International Symposium, {ISAAC}
2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5878},
pages = {647--656},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-10631-6\_66},
doi = {10.1007/978-3-642-10631-6\_66},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/ChenT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0903-4728,
author = {Jin{-}yi Cai and
Xi Chen and
Pinyan Lu},
title = {Graph Homomorphisms with Complex Values: {A} Dichotomy Theorem},
journal = {CoRR},
volume = {abs/0903.4728},
year = {2009},
url = {http://arxiv.org/abs/0903.4728},
eprinttype = {arXiv},
eprint = {0903.4728},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0903-4728.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0904-0644,
author = {Xi Chen and
Decheng Dai and
Ye Du and
Shang{-}Hua Teng},
title = {Settling the Complexity of Arrow-Debreu Equilibria in Markets with
Additively Separable Utilities},
journal = {CoRR},
volume = {abs/0904.0644},
year = {2009},
url = {http://arxiv.org/abs/0904.0644},
eprinttype = {arXiv},
eprint = {0904.0644},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0904-0644.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0907-4130,
author = {Xi Chen and
Shang{-}Hua Teng},
title = {Spending is not Easier than Trading: On the Computational Equivalence
of Fisher and Arrow-Debreu Equilibria},
journal = {CoRR},
volume = {abs/0907.4130},
year = {2009},
url = {http://arxiv.org/abs/0907.4130},
eprinttype = {arXiv},
eprint = {0907.4130},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0907-4130.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BarakBCR09,
author = {Boaz Barak and
Mark Braverman and
Xi Chen and
Anup Rao},
title = {Direct Sums in Randomized Communication Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-044}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/044},
eprinttype = {ECCC},
eprint = {TR09-044},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BarakBCR09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ChenD08,
author = {Xi Chen and
Xiaotie Deng},
title = {Matching algorithmic bounds for finding a Brouwer fixed point},
journal = {J. {ACM}},
volume = {55},
number = {3},
pages = {13:1--13:26},
year = {2008},
url = {https://doi.org/10.1145/1379759.1379761},
doi = {10.1145/1379759.1379761},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/ChenD08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/ChenST08,
author = {Xi Chen and
Xiaoming Sun and
Shang{-}Hua Teng},
editor = {Xiaodong Hu and
Jie Wang},
title = {Quantum Separation of Local Search and Fixed Point Computation},
booktitle = {Computing and Combinatorics, 14th Annual International Conference,
{COCOON} 2008, Dalian, China, June 27-29, 2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5092},
pages = {170--179},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-69733-6\_18},
doi = {10.1007/978-3-540-69733-6\_18},
timestamp = {Wed, 26 Apr 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/ChenST08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/CaiCL08,
author = {Jin{-}yi Cai and
Xi Chen and
Dong Li},
editor = {Cynthia Dwork},
title = {A quadratic lower bound for the permanent and determinant problem
over any characteristic != 2},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {491--498},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374446},
doi = {10.1145/1374376.1374446},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/CaiCL08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/ChenD08,
author = {Xi Chen and
Xiaotie Deng},
editor = {Ming{-}Yang Kao},
title = {Complexity of Bimatrix Nash Equilibria},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_79},
doi = {10.1007/978-0-387-30162-4\_79},
timestamp = {Thu, 27 Jun 2019 16:25:31 +0200},
biburl = {https://dblp.org/rec/reference/algo/ChenD08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/ChenD08a,
author = {Xi Chen and
Xiaotie Deng},
editor = {Ming{-}Yang Kao},
title = {Incentive Compatible Selection},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_185},
doi = {10.1007/978-0-387-30162-4\_185},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/ChenD08a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/ChenD08b,
author = {Xi Chen and
Xiaotie Deng},
editor = {Ming{-}Yang Kao},
title = {Non-approximability of Bimatrix Nash Equilibria},
booktitle = {Encyclopedia of Algorithms - 2008 Edition},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-0-387-30162-4\_258},
doi = {10.1007/978-0-387-30162-4\_258},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/ChenD08b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/csr/ChenD07,
author = {Xi Chen and
Xiaotie Deng},
title = {Recent development in computational complexity characterization of
Nash equilibrium},
journal = {Comput. Sci. Rev.},
volume = {1},
number = {2},
pages = {88--99},
year = {2007},
url = {https://doi.org/10.1016/j.cosrev.2007.09.002},
doi = {10.1016/J.COSREV.2007.09.002},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/csr/ChenD07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/ChengCY07,
author = {Yongxi Cheng and
Xi Chen and
Yiqun Lisa Yin},
title = {On searching a table consistent with division poset},
journal = {Theor. Comput. Sci.},
volume = {370},
number = {1-3},
pages = {240--253},
year = {2007},
url = {https://doi.org/10.1016/j.tcs.2006.10.027},
doi = {10.1016/J.TCS.2006.10.027},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/ChengCY07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/LiuXXJ07,
author = {Lan Liu and
Xi Chen and
Jing Xiao and
Tao Jiang},
title = {Complexity and approximation of the minimum recombinant haplotype
configuration problem},
journal = {Theor. Comput. Sci.},
volume = {378},
number = {3},
pages = {316--330},
year = {2007},
url = {https://doi.org/10.1016/j.tcs.2007.02.036},
doi = {10.1016/J.TCS.2007.02.036},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/LiuXXJ07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cpm/ZhangCL07,
author = {Jing Zhang and
Xi Chen and
Ming Li},
editor = {Bin Ma and
Kaizhong Zhang},
title = {Computing Exact p-Value for Structured Motif},
booktitle = {Combinatorial Pattern Matching, 18th Annual Symposium, {CPM} 2007,
London, Canada, July 9-11, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4580},
pages = {162--172},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-73437-6\_18},
doi = {10.1007/978-3-540-73437-6\_18},
timestamp = {Mon, 13 Mar 2023 16:58:28 +0100},
biburl = {https://dblp.org/rec/conf/cpm/ZhangCL07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenT07,
author = {Xi Chen and
Shang{-}Hua Teng},
title = {Paths Beyond Local Search: {A} Tight Bound for Randomized Fixed-Point
Computation},
booktitle = {48th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2007), October 20-23, 2007, Providence, RI, USA, Proceedings},
pages = {124--134},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/FOCS.2007.14},
doi = {10.1109/FOCS.2007.14},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenT07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenTV07,
author = {Xi Chen and
Shang{-}Hua Teng and
Paul Valiant},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {The approximation complexity of win-lose games},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {159--168},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283401},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenTV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0704-1678,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
title = {Settling the Complexity of Computing Two-Player Nash Equilibria},
journal = {CoRR},
volume = {abs/0704.1678},
year = {2007},
url = {http://arxiv.org/abs/0704.1678},
eprinttype = {arXiv},
eprint = {0704.1678},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0704-1678.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0702088,
author = {Xi Chen and
Shang{-}Hua Teng},
title = {Paths Beyond Local Search: {A} Nearly Tight Bound for Randomized Fixed-Point
Computation},
journal = {CoRR},
volume = {abs/cs/0702088},
year = {2007},
url = {http://arxiv.org/abs/cs/0702088},
eprinttype = {arXiv},
eprint = {cs/0702088},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0702088.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaim/ChenD06,
author = {Xi Chen and
Xiaotie Deng},
editor = {Siu{-}Wing Cheng and
Chung Keung Poon},
title = {Lattice Embedding of Direction-Preserving Correspondence over Integrally
Convex Set},
booktitle = {Algorithmic Aspects in Information and Management, Second International
Conference, {AAIM} 2006, Hong Kong, China, June 20-22, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4041},
pages = {53--63},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11775096\_7},
doi = {10.1007/11775096\_7},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/aaim/ChenD06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/ChenD06,
author = {Xi Chen and
Xiaotie Deng},
editor = {Danny Z. Chen and
D. T. Lee},
title = {A Simplicial Approach for Discrete Fixed Point Theorems},
booktitle = {Computing and Combinatorics, 12th Annual International Conference,
{COCOON} 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4112},
pages = {3--12},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11809678\_3},
doi = {10.1007/11809678\_3},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/ChenD06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/ChenDL06,
author = {Xi Chen and
Xiaotie Deng and
Becky Jie Liu},
editor = {Danny Z. Chen and
D. T. Lee},
title = {On Incentive Compatible Competitive Selection Protocol},
booktitle = {Computing and Combinatorics, 12th Annual International Conference,
{COCOON} 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4112},
pages = {13--22},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11809678\_4},
doi = {10.1007/11809678\_4},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/ChenDL06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenD06,
author = {Xi Chen and
Xiaotie Deng},
title = {Settling the Complexity of Two-Player Nash Equilibrium},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {261--272},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.69},
doi = {10.1109/FOCS.2006.69},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenD06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChenDT06,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
title = {Computing Nash Equilibria: Approximation and Smoothed Complexity},
booktitle = {47th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2006), 21-24 October 2006, Berkeley, California, USA, Proceedings},
pages = {603--612},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/FOCS.2006.20},
doi = {10.1109/FOCS.2006.20},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChenDT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ChenD06,
author = {Xi Chen and
Xiaotie Deng},
editor = {Michele Bugliesi and
Bart Preneel and
Vladimiro Sassone and
Ingo Wegener},
title = {On the Complexity of 2D Discrete Fixed Point Problem},
booktitle = {Automata, Languages and Programming, 33rd International Colloquium,
{ICALP} 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {4051},
pages = {489--500},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11786986\_43},
doi = {10.1007/11786986\_43},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ChenD06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wine/ChenDT06,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
editor = {Paul G. Spirakis and
Marios Mavronicolas and
Spyros C. Kontogiannis},
title = {Sparse Games Are Hard},
booktitle = {Internet and Network Economics, Second International Workshop, {WINE}
2006, Patras, Greece, December 15-17, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4286},
pages = {262--273},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11944874\_24},
doi = {10.1007/11944874\_24},
timestamp = {Fri, 27 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/wine/ChenDT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/wine/ChenHT06,
author = {Xi Chen and
Li{-}Sha Huang and
Shang{-}Hua Teng},
editor = {Paul G. Spirakis and
Marios Mavronicolas and
Spyros C. Kontogiannis},
title = {Market Equilibria with Hybrid Linear-Leontief Utilities},
booktitle = {Internet and Network Economics, Second International Workshop, {WINE}
2006, Patras, Greece, December 15-17, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4286},
pages = {274--285},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11944874\_25},
doi = {10.1007/11944874\_25},
timestamp = {Wed, 21 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/wine/ChenHT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0602043,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
title = {Computing Nash Equilibria: Approximation and Smoothed Complexity},
journal = {CoRR},
volume = {abs/cs/0602043},
year = {2006},
url = {http://arxiv.org/abs/cs/0602043},
eprinttype = {arXiv},
eprint = {cs/0602043},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0602043.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenD06,
author = {Xi Chen and
Xiaotie Deng},
title = {On the Complexity of 2D Discrete Fixed Point Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-037}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-037/index.html},
eprinttype = {ECCC},
eprint = {TR06-037},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenD06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChenDT06,
author = {Xi Chen and
Xiaotie Deng and
Shang{-}Hua Teng},
title = {Computing Nash Equilibria: Approximation and Smoothed Complexity},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-023}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-023/index.html},
eprinttype = {ECCC},
eprint = {TR06-023},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChenDT06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/LiuCXJ05,
author = {Lan Liu and
Xi Chen and
Jing Xiao and
Tao Jiang},
editor = {Xiaotie Deng and
Ding{-}Zhu Du},
title = {Complexity and Approximation of the Minimum Recombination Haplotype
Configuration Problem},
booktitle = {Algorithms and Computation, 16th International Symposium, {ISAAC}
2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3827},
pages = {370--379},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11602613\_38},
doi = {10.1007/11602613\_38},
timestamp = {Thu, 23 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/isaac/LiuCXJ05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChenD05,
author = {Xi Chen and
Xiaotie Deng},
editor = {Harold N. Gabow and
Ronald Fagin},
title = {On algorithms for discrete and approximate brouwer fixed points},
booktitle = {Proceedings of the 37th Annual {ACM} Symposium on Theory of Computing,
Baltimore, MD, USA, May 22-24, 2005},
pages = {323--330},
publisher = {{ACM}},
year = {2005},
url = {https://doi.org/10.1145/1060590.1060638},
doi = {10.1145/1060590.1060638},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/ChenD05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-cs-0505075,
author = {Yongxi Cheng and
Xi Chen and
Yiqun Lisa Yin},
title = {On Searching a Table Consistent with Division Poset},
journal = {CoRR},
volume = {abs/cs/0505075},
year = {2005},
url = {http://arxiv.org/abs/cs/0505075},
eprinttype = {arXiv},
eprint = {cs/0505075},
timestamp = {Wed, 19 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-cs-0505075.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-134,
author = {Xi Chen and
Xiaotie Deng},
title = {3-NASH is PPAD-Complete},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-134}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-134/index.html},
eprinttype = {ECCC},
eprint = {TR05-134},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-134.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-140,
author = {Xi Chen and
Xiaotie Deng},
title = {Settling the Complexity of 2-Player Nash-Equilibrium},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-140}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-140/index.html},
eprinttype = {ECCC},
eprint = {TR05-140},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-140.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
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.
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
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
