I am a graduated student at MIT, advised by Ryan Williams.

I have a broad interest in theoretical computer science. In particular, I am interested in Computational Complexity and Fine-Grained Complexity.

My new personal website at MIT (Stopped update this since  5/31/2018)




Selected Publications:
      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]

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.

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.
Towards Instance Optimal Bounds for Best Arm Identification.
Lijie Chen, Jian Li, Mingda Qiao.
Conference on Learning Theory (COLT 2017).

Manuscripts:
Fine-grained Complexity Meets IP = PSPACE
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein

Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits
Lijie Chen.

Full Publications and Manuscripts:

Published or Accepted:
2018:        
        Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures.
           Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu. 
           Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018).
           [arxiv]

        Improved Algorithms for Maintaining DFS Tree in Undirected Graphs. 
           Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang.        
           Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018).
           [arxiv]

        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]
2017:
Bounded rationality of restricted Turing machines. 
Lijie Chen, Pingzhong Tang, Ruosong Wang. 
AAAI 2017. 

K-Memory Strategies in Repeated Games.
Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang.
Extended abstract, International Conference on Antonomous Agents and Multiagent Sytems
 (AAMAS 2017)

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection. 
Lijie Chen, Jian Li, Mingda Qiao.
International Conference on Artificial Intelligence and Statistics (AISTATS 2017).
[arxiv]  [conference version]

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.

Towards Instance Optimal Bounds for Best Arm Identification.
Lijie Chen, Jian Li, Mingda Qiao.
Conference on Learning Theory (COLT 2017).

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.
Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang
Conference on Learning Theory (COLT 2017).
[arxiv]

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 SICOMP Special Issue for FOCS 2017.
2016:
Pure Exploration of Multi-armed Bandit Under Matroid Constraints.
Lijie Chen, Anupum Gupta, Jian Li. 
Conference on Learning Theory (COLT 2016).
[arxiv] [slides] [conference version]

Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy
Conjecture. 
Lijie Chen, Jian Li. 
Conference on Learning Theory Open Problem (COLT 2016 Open Problem).
[arxiv] [slides] [conference version]

Adaptivity vs Postselection. 
Lijie Chen. 
International Symposium on Algorithm and Computation (ISAAC 2016).
Best Student Paper Award

Old Manuscripts:    
On the Optimal Sample Complexity for Best Arm Identification. 
Lijie Chen, Jian Li. 

A Note on Oracle Separations for BQP. 
Lijie Chen. 
[arxiv]

Awards:

1. 2013 International Olympiad in Informatics, Gold medal, First Place.

2. 2014 ACM-ICPC world finals, Bronze medal, 11th Place (with Qiwei Feng, Qinshi Wang).

3. 2016 ISAAC Best Student Paper.                    

4. 2017 ACM-ICPC world finals, Silver medal, 6th place (with Yuhao Du, Ce Jin).