Lijie Chen

Research Interests: Theoretical Computer Science

I have a broad interest in theoretical computer science. In particular, I am interested in Computational Complexity and Fine-Grained Complexity.

I am currently a fourth year graduate student at MIT, and I am very fortunate to be advised by Ryan Williams. Prior to that, I received my bachelor's degree from Yao Class at Tsinghua University.

At Tsinghua University, I was advised by Prof. Jian Li, working on Multi-Armed Bandits. During the Spring of 2016, I was visiting MIT, working under the supervision of Prof. Scott Aaronson on Quantum Complexity. [CV]

I was visiting Simons Institute in the Fall of 2018.

Twitter

Some of my projects:

• Algorithmic Method for Proving Circuit Lower Bounds

• Optimal Derandomization from Hardness Assumptions

• Hardness Magnification

Submitted / Manuscripts

Selected Publications

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

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

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

• Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization [eccc] [slides at Simons (for complexity theorist)] [slides at IAS (intense version)] [slides at Warwick (lightweight version)]
  Lijie Chen, Hanlin Ren
  Symposium on the Theory of Computing (STOC 2020). Invited to the SICOMP Special Issue for STOC 2020
  

• Beyond Natural Proofs: Hardness Magnification and Locality [eccc] [arxiv] [notes by Igor]
  Lijie Chen, Shuichi Hirahara,Igor Oliveira, Jan Pich, Ninad Rajgopal, Rahul Santhanam
  Innovations in Theoretical Computer Science (ITCS 2020)
  

• Efficient Construction of Rigid Matrices Using an NP Oracle [pdf] [slides] [Oded's choice]
  Josh Alman, Lijie Chen
  Foundations of Computer Science (FOCS 2019). Machtey Award for Best Student Paper. Invited to the SICOMP Special Issue for FOCS 2019
  

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

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

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

Full Publications