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

Selected Publications

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

  • Sharp Threshold Results for Computational Complexity
    Lijie Chen, Ce Jin, Ryan Williams
    Symposium on the Theory of Computing (STOC 2020)
    [eccc]

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

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

Summary

We showed (among many other things) finding the furthest pair among n points in 2^(log* n) dimensional Euclidian space
requires essentialy n^2 time under SETH. We also use the sqrt(n) BQP communication protocol for Set-Disjointness to establish
inapproximbility results for problems in P.

  • Complexity-Theoretic Foundations of Quantum Supremacy Experiments
    Scott Aaronson, Lijie Chen
    Computational Complexity Conference (CCC 2017)
    Invited to the Toc Special Issue for CCC 2017
    [eccc] [arxiv] [slides]

Summary

We studied the general theoretical foundations for demonstrating “quantum supremacy” with near-term quantum devices.

Submitted / Manuscripts

  • On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
    Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
    [eccc]

Full Publications