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.
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]
Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
Lijie Chen
[Talk at UT Austin's Theory Seminar]
Foundations of Computer Science (FOCS 2019)
[eccc]
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]
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Lijie Chen
Computational Complexity Conference (CCC 2018)
Invited to the Toc Special Issue for CCC 2018
[eccc] [arxiv] [slides] [draft of journal version]
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]
We studied the general theoretical foundations for demonstrating “quantum supremacy” with near-term quantum devices.
On The Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
Foundations of Computer Science (FOCS 2017)
Invited to the SICOMP Special Issue for FOCS 2017
[eccc] [arxiv] [slides]
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