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

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] [short highlight]

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

Manuscripts

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

Selected Publications

  • Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor] [short highlight]
    Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira
    International Colloquium on Automata, Languages and Programming (ICALP), 2021

  • Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma [paper] [eccc] [video by Xin Lyu at STOC 2021] [short highlight]
    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 by me] [slides by Roei] [short highlight]
    [longer summary]
    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] [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

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

  • 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

  • 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

  • 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

  • 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