|
Publications (by Years)
Google Scholar Page
2020
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor Oliveira, Jan Pich, Ninad Rajgopal, Rahul Santhanam
Innovations in Theoretical Computer Science (ITCS 2020)
[eccc] [arxiv]
2019
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
Lijie Chen, Ryan Williams
Computational Complexity Conference (CCC 2019)
This paper subsumes a previous manuscript [arxiv]
[slides] [proceeding version]
Summary
Unlike the well-known APSP equivalent class, few OV-hard problems are known to be equivalent to OV. In this paper,
we showed several natural problems are equivalent to O(log n) dimensional OV. Two most interesting problems are: approximate
bichromatic closest pair and O(log n) dimensional Maximum Inner Product. In order to get reductions from these problems to OV,
we make use of Sigma_2 communication protocols and Locality Sensitivity Hashing. Our results also apply to the data structure
setting, in which we show that Partial Match and Nearest Neighbor Search are equivalent in a certain sense.
Summary
We applied the classical result IP = PSPACE to obtain equivalence results for problems in P.
2018
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
[arxiv]
Improved Algorithms for Maintaining DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
[arxiv]
Summary
We showed (among many other things) finding the furthest pair among n points in 2^(log* n) dimensional Euclidian space
requires essentialy n^2 time under SETH. We also use the sqrt(n) BQP communication protocol for Set-Disjointness to establish
inapproximbility results for problems in P.
2017
On The Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
Foundations of Computer Science (FOCS 2017)
Invited to the SICOMP Special Issue for FOCS 2017
[eccc] [arxiv] [slides]
Summary
We constructed oracle separations between SZK and PP, PZK and SZK and NISZK and NIPZK, answering several open questions.
We also showed a communication complexity class separation between NISZK and UPP.
Summary
We made a step toward a complete understanding of the optimal sample complexity of the fundemental Best-1-Arm problem.
Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang
Conference on Learning Theory (COLT 2017)
[arxiv] [conference version]
Summary
We studied the general theoretical foundations for demonstrating “quantum supremacy” with near-term quantum devices.
Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
Lijie Chen, Jian Li, Mingda Qiao
International Conference on Artificial Intelligence and Statistics (AISTATS 2017)
[arxiv] [conference version]
Summary: We showed tighter lower bounds and upper bounds for the Best-k-Arm problem, with a gap of a doubly-logarithmic factor.
K-Memory Strategies in Repeated Games
Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang
Extended abstract, International Conference on Antonomous Agents and Multiagent Sytems (AAMAS 2017)
2016
Notes
Old Manuscripts
|