Research
Home
Publications (by Years)
Publications (by Categories)
About Me
Talks
Projects
Expositions

Publications and Manuscripts (by Categories)

Google Scholar Page

Links:

Computational Complexity

  • Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
    Lijie Chen, Xin Lyu, Ryan Williams
    Foundations of Computer Science (FOCS 2020)
    [eccc]
    [video by Xin Lyu in FOCS 2020]

  • On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
    Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
    Foundations of Computer Science (FOCS 2020)
    [eccc] [video by Roei Tell in FOCS 2020]

  • Sharp Threshold Results for Computational Complexity
    Lijie Chen, Ce Jin, Ryan Williams
    Symposium on the Theory of Computing (STOC 2020)
    [eccc] [slides]

  • Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
    Lijie Chen, Hanlin Ren
    Symposium on the Theory of Computing (STOC 2020)
    [slides] [eccc]

  • 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]

  • Efficient Construction of Rigid Matrices Using an NP Oracle
    Josh Alman, Lijie Chen
    Foundations of Computer Science (FOCS 2019)
    Machtey Award for Best Student Paper
    [pdf] [slides]

  • Hardness Magnification for all Sparse NP Languages
    Lijie Chen, Ce Jin, Ryan Williams
    Foundations of Computer Science (FOCS 2019)
    [eccc]

  • 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]

  • Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds
    Lijie Chen, Roei Tell
    Symposium on the Theory of Computing (STOC 2019)
    Danny Lewin Best Student Paper Award
    [eccc] [Oded's choice] [slides]

  • 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.

Fine-Grained Complexity
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.

  • 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]

  • On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
    Lijie Chen
    Computational Complexity Conference (CCC 2018)
    Invited to the Toc Special Issue for CCC 2018
    [eccc] [arxiv] [slides]
    [journal version]

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.

Multi-Armed Bandits
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]

  • 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.

  • Pure Exploration of Multi-armed Bandit Under Matroid Constraints
    Lijie Chen, Anupum Gupta, Jian Li
    Conference on Learning Theory (COLT 2016)
    [arxiv] [conference version] [slides]

  • Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
    Lijie Chen, Jian Li
    Conference on Learning Theory Open Problem (COLT 2016 Open Problem)
    [arxiv] [conference version] [slides]

  • On the Optimal Sample Complexity for Best Arm Identification
    Lijie Chen, Jian Li
    [arxiv]

Quantum Complexity Theory
Summary

We studied the general theoretical foundations for demonstrating “quantum supremacy” with near-term quantum devices.

  • A Note on Oracle Separations for BQP
    Lijie Chen
    [arxiv]

Game Theory

  • 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)

  • Bounded rationality of restricted Turing machines
    Lijie Chen, Pingzhong Tang, Ruosong Wang
    AAAI 2017
    [conference version]

Algorithms

  • 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]

  • Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
    Lijie Chen, Ruosong Wang
    Innovations in Theoretical Computer Science (ITCS 2019)
    [arxiv] [slides]

Distributed Computing

  • Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
    Lijie Chen, Ofer Grossman
    Symposium on Principles of Distributed Computing (PODC 2019)
    [eccc]

Differential Privacy

Theses

  • Fine-Grained Complexity Meets Communication Complexity
    Master Thesis
    [pdf]