Lijie Chen

Lijie Chen 

Photo by Toru

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 of Recent Work

  • On Distributed Differential Privacy and Counting Distinct Elements [arxiv] [long slides] [short slides] [summary]

  • Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost [eccc] [slides by me] [slides by Roei] [video by Roei Tell at STOC 2021] [short highlight]
    [longer summary]

  • Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [eccc] [video by Xin Lyu at FOCS 2020] [slides by Ryan] [short highlight]

  • Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor] [video by Xin] [short highlight]

  • Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability [eccc] [video by Raghuvansh Saxena at STOC 2021] [short highlight]

Selected Publications

Derandomization

  • Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [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

  • Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits [Talk at UT Austin's Theory Seminar] [eccc]
    Lijie Chen. Foundations of Computer Science (FOCS 2019). Invited to the SICOMP Special Issue for FOCS 2019

  • 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