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

  • Hardness Magnification for all Sparse NP Languages
    Lijie Chen, Ce Jin, Ryan Williams
    Foundations of Computer Science (FOCS 2019)
    [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
    [pdf] [slides]

Summary

We proved that there is a language in NQP (non-deterministic quasi-polynomial time) which cannot be 12+1polylog(n) approximated by polynomial-size ACC^0 circuits. Our method can also be used to prove inapproximability results for other circuit class if non-trivial SAT (or GAP-UNSAT) algorithms for them are discovered. One interesting remark is that the proof crucially relies on Barrington's theorem.

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

Summary

We constructed oracle separations between SZK and PP, PZK and SZK and NISZK and NIPZK, answering several open questions.
We also showed a communication complexity class separation between NISZK and UPP.

Submitted / Manuscripts

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

  • Strong Average-Case Lower Bounds from Non-trivial Derandomization
    Lijie Chen, Hanlin Ren

Full Publications