Publications and Manuscripts (by Categories)
Google Scholar Page
Links:
Computational Complexity
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Foundations of Computer Science (FOCS 2021)
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [slides]
Lijie Chen, Roei Tell
Foundations of Computer Science (FOCS 2021)
Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor]
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira
International Colloquium on Automata, Languages and Programming (ICALP), 2021
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
Foundations of Computer Science (FOCS 2020)
[eccc]
[video by Roei Tell in FOCS 2020]
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor Oliveira, Jan Pich, Ninad Rajgopal, Rahul Santhanam
Innovations in Theoretical Computer Science (ITCS 2020)
[eccc] [arxiv]
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
Lijie Chen, Ryan Williams
Computational Complexity Conference (CCC 2019)
This paper subsumes a previous manuscript [arxiv]
[slides] [proceeding version]
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]
Fine-Grained Complexity
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]
Streaming Algorithms/Complexity
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability [eccc]
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Symposium on the Theory of Computing (STOC 2021)
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs [arxiv]
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
International Colloquium on Automata, Languages and Programming (ICALP), 2021
Multi-Armed Bandits
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] [conference version]
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]
Quantum Complexity Theory
Game Theory
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)
Algorithms
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]
Distributed Computing
Differential Privacy
|