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

• Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost
  Lijie Chen, Roei Tell
  [eccc] [Oded's choice]
  [slides]
  

Selected Publications

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

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

• 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]
  [notes by Igor]
  

• 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
  Invited to the SICOMP Special Issue for FOCS 2019
  [pdf] [slides] [Oded's choice]
  

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

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

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

Full Publications