Publications and Manuscripts (by Categories)

Google Scholar Page

Links:

• Computational Complexity

• Fine-Grained Complexity

• Multi-Armed Bandits

• Quantum Complexity Theory

Computational Complexity

• Constructive Separations and Their Consequences
  Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
  Foundations of Computer Science (FOCS 2021)
  

• Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [slides]
  Lijie Chen, Roei Tell
  Foundations of Computer Science (FOCS 2021)
  

• Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor]
  Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira
  International Colloquium on Automata, Languages and Programming (ICALP), 2021
  

• Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost
  Lijie Chen, Roei Tell
  Symposium on the Theory of Computing (STOC 2021)
  [eccc] [Oded's choice]
  [slides]
  

• Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma
  Lijie Chen, Xin Lyu
  Symposium on the Theory of Computing (STOC 2021)
  [paper] [eccc]
  

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

• Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
  Lijie Chen
  [Talk at UT Austin's Theory Seminar]
  Foundations of Computer Science (FOCS 2019)
  [eccc] [draft of journal version]
  

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

• Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems
  Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams
  Computational Complexity Conference (CCC 2019)
  [eccc] [proceeding version]
  

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

Fine-Grained Complexity

• An Equivalence Class for Orthogonal Vectors
  Lijie Chen, Ryan Williams
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
  [proceeding version] [full version] [slides]
  

• Fine-grained Complexity Meets IP = PSPACE
  Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
  [arxiv]
  

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

Streaming Algorithms/Complexity

• Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability [eccc]
  Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
  Symposium on the Theory of Computing (STOC 2021)
  

• Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs [arxiv]
  Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
  International Colloquium on Automata, Languages and Programming (ICALP), 2021
  

Multi-Armed Bandits

• Towards Instance Optimal Bounds for Best Arm Identification
  Lijie Chen, Jian Li, Mingda Qiao
  Conference on Learning Theory (COLT 2017)
  [arxiv] [conference version]
  

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

• 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

• Complexity-Theoretic Foundations of Quantum Supremacy Experiments
  Scott Aaronson, Lijie Chen
  Computational Complexity Conference (CCC 2017)
  Invited to the Toc Special Issue for CCC 2017
  [eccc] [arxiv] [slides] [conference version]
  

• Adaptivity vs Postselection
  Lijie Chen
  International Symposium on Algorithm and Computation (ISAAC 2016)
  Best Student Paper Award
  [arxiv] [conference version] [slides]
  

• 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

• On Distributed Differential Privacy and Counting Distinct Elements
  Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
  Innovations in Theoretical Computer Science (ITCS 2021)
  [arxiv]