Lijie ChenResearch Interests: Theoretical Computer Science 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 MultiArmed 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
Summary
We proved that there is a language in NQP (nondeterministic quasipolynomial time) which cannot be 12+1polylog(n) approximated by polynomialsize ACC^0 circuits. Our method can also be used to prove inapproximability results for other circuit class if nontrivial SAT (or GAPUNSAT) algorithms for them are discovered. One interesting remark is that the proof crucially relies on Barrington's theorem.
Summary
We showed (among many other things) finding the furthest pair among n points in 2^(log* n) dimensional Euclidian space
Summary
We studied the general theoretical foundations for demonstrating “quantum supremacy” with nearterm quantum devices.
Summary
We constructed oracle separations between SZK and PP, PZK and SZK and NISZK and NIPZK, answering several open questions. Submitted / Manuscripts
Full Publications
