Lijie Chen

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:

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)

  • 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