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 fifth-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

Note: Click on [summary] or [highlight] to view summaries or highlight of the papers/projects!

Some of my projects:

Video/Slides/Summary of Recent Work

  • Derandomization and its connections throughout complexity theory, a three-part series presented together with Roei Tell at IAS. [First talk by Roei] [Second talk by me] [Notes on the second talk] [Third talk by Roei] [summary]

  • Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions [arxiv] [abstract]

  • Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [slides by me] [slides by Roei] [short summary]

Selected Publications

Derandomization

  • Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [slides] [Roei's talk at TCS plus] [Roei's slides] [short summary]
    Lijie Chen, Roei Tell. Foundations of Computer Science (FOCS 2021). Invited to the SICOMP Special Issue for FOCS 2021

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

Circuit Lower Bounds from Algorithms

  • Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [eccc] [video by Xin Lyu in FOCS 2020] [slides by Ryan] [short highlight]
    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)] [short highlight]
    Lijie Chen, Hanlin Ren. Symposium on the Theory of Computing (STOC 2020). Invited to the SICOMP Special Issue for STOC 2020

  • Efficient Construction of Rigid Matrices Using an NP Oracle [pdf] [slides] [Oded's choice] [short highlight]
    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

Hardness Magnification (Strong Lower Bounds from Much Weaker Lower Bounds)

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

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

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

Other Topics

  • (Quantum Supremacy) 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

  • (Streaming Lower Bounds) 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). Invited to the SICOMP Special Issue for STOC 2021

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

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

Full Publications