Lijie Chen

Random Photo

Research Interests: Theoretical Computer Science

I have a broad interest in theoretical computer science. In particular, I am interested in classical and quantum computational complexity theory and their connections to other fields of computer science and quantum physics.

I am joining Berkeley EECS as an Assistant Professor in Fall 2025. [Read about how to apply.]

I am a Miller Postdoctoral Fellow at UC Berkeley, hosted by Avishay Tal and Umesh V. Vazirani. I got my Ph.D. from MIT, and I was 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]

Twitter

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

Video/Slides/Summary of Recent Work

Workshops

  • Frontiers in Complexity Theory: A Graduate Workshop organized by Roei Tell, Ryan Williams, and myself [site with videos]

  • FOCS23 workshop on explicit construction organized by Igor C. Oliveira, Rahul Santhanam, and myself [site]

  • FOCS22 workshop on derandomization organized by Roei Tell and myself: [site with videos]

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

Manuscripts

  • Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin [eccc]
    Lijie Chen, Jiatu Li, Jingxun Liang

  • On the unprovability of circuit size bounds in intuitionistic S12 [arxiv]
    Lijie Chen, Jiatu Li, Igor C. Oliveira

  • Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?) [eccc]
    Lijie Chen, Ron D. Rothblum, Roei Tell

  • Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary [arxiv]
    Chris Akers, Adam Bouland, Lijie Chen, Tamara Kohler, Tony Metger, Umesh Vazirani

Selected Publications

Derandomization

  • Polynomial-Time Pseudodeterministic Construction of Primes [eccc] [my slides] [Quanta Magazine]
    Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
    Foundations of Computer Science (FOCS 2023)

  • Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization [eccc]
    Lijie Chen, Roei Tell, Ryan Williams
    Foundations of Computer Science (FOCS 2023)

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

  • 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
    [SIAM Journal on Computing]

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)
    [Journal of the ACM]

  • 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