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 ChenErik 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 ChenRan DuanRuosong WangHanrui 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]