Bounded Rationality of Restricted Turing Machines. - Lijie Chen 001; Pingzhong Tang (AAMAS, 2015)

On the Optimal Sample Complexity for Best Arm Identification. - Lijie Chen 001; Jian Li 015 (CoRR, 2015)

Pure Exploration of Multi-armed Bandit Under Matroid Constraints. - Lijie Chen 001; Anupam Gupta 001; Jian Li 015 (COLT, 2016)

Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture. - Lijie Chen 001; Jian Li 015 (COLT, 2016)

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation. - Lijie Chen 001 (ISAAC, 2016)

A Note on Oracle Separations for BQP. - Lijie Chen 001 (CoRR, 2016)

Adaptivity vs Postselection. - Lijie Chen 001 (CoRR, 2016)

Improved Algorithms for Maintaining DFS Tree in Undirected Graphs. - Lijie Chen 001; Ran Duan; Ruosong Wang; Hanrui Zhang 001 (CoRR, 2016)

Complexity-Theoretic Foundations of Quantum Supremacy Experiments. - Scott Aaronson; Lijie Chen 001 (Electron. Colloquium Comput. Complex., 2016)

On SZK and PP. - Adam Bouland; Lijie Chen 001; Dhiraj Holden; Justin Thaler; Prashant Nalini Vasudevan (Electron. Colloquium Comput. Complex., 2016)

Bounded Rationality of Restricted Turing Machines. - Lijie Chen 001; Pingzhong Tang; Ruosong Wang (AAAI, 2017)

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection. - Lijie Chen 001; Jian Li 015; Mingda Qiao (AISTATS, 2017)

K-Memory Strategies in Repeated Games. - Lijie Chen 001; Fangzhen Lin; Pingzhong Tang; Kangning Wang 001; Ruosong Wang; Shiheng Wang (AAMAS, 2017)

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration. - Lijie Chen 001; Anupam Gupta 001; Jian Li 015; Mingda Qiao; Ruosong Wang (COLT, 2017)

Towards Instance Optimal Bounds for Best Arm Identification. - Lijie Chen 001; Jian Li 015; Mingda Qiao (COLT, 2017)

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. - Lijie Chen 001; Erik D. Demaine; Yuzhou Gu; Virginia Vassilevska Williams; Yinzhan Xu; Yuancheng Yu (SWAT, 2018)

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. - Lijie Chen 001; Ran Duan; Ruosong Wang; Hanrui Zhang 001; Tianyi Zhang 008 (SWAT, 2018)

Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. - Lijie Chen 001 (CoRR, 2018)

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. - Lijie Chen 001 (Electron. Colloquium Comput. Complex., 2018)

Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds. - Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2018)

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. - Lijie Chen 001; R. Ryan Williams (CCC, 2019)

Efficient Construction of Rigid Matrices Using an NP Oracle. - Josh Alman; Lijie Chen 001 (FOCS, 2019)

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. - Lijie Chen 001; Ruosong Wang (ITCS, 2019)

Fine-grained Complexity Meets IP = PSPACE. - Lijie Chen 001; Shafi Goldwasser; Kaifeng Lyu; Guy N. Rothblum; Aviad Rubinstein (SODA, 2019)

An Equivalence Class for Orthogonal Vectors. - Lijie Chen 001; Ryan Williams 001 (SODA, 2019)

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits. - Lijie Chen 001 (Electron. Colloquium Comput. Complex., 2019)

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators. - Lijie Chen 001; Ofer Grossman (Electron. Colloquium Comput. Complex., 2019)

Hardness Magnification for all Sparse NP Languages. - Lijie Chen 001; Ce Jin 001; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2019)

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. - Lijie Chen 001; Dylan M. McKay; Cody Murray; R. Ryan Williams (Electron. Colloquium Comput. Complex., 2019)

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds. - Lijie Chen 001; Ron Rothblum; Roei Tell; Eylon Yogev (Electron. Colloquium Comput. Complex., 2019)

Beyond Natural Proofs: Hardness Magnification and Locality. - Igor Carboni Oliveira; Lijie Chen 001; Shuichi Hirahara; Ján Pich; Ninad Rajgopal; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2019)

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. - Lijie Chen 001; Ron D. Rothblum; Roei Tell; Eylon Yogev (FOCS, 2020)

Strong average-case lower bounds from non-trivial derandomization. - Lijie Chen 001; Hanlin Ren (STOC, 2020)

Sharp Threshold Results for Computational Complexity. - Lijie Chen 001; Ce Jin 001; R. Ryan Williams (Electron. Colloquium Comput. Complex., 2020)

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. - Lijie Chen 001; Xin Lyu 002; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2020)

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. - Lijie Chen 001; Hanlin Ren (Electron. Colloquium Comput. Complex., 2020)

Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. - Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2020)

On the Power of Statistical Zero Knowledge. - Adam Bouland; Lijie Chen 001; Dhiraj Holden; Justin Thaler; Prashant Nalini Vasudevan (SIAM J. Comput., 2020)

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. - Lijie Chen 001; Gillat Kol; Dmitry Paramonov; Raghuvansh R. Saxena; Zhao Song 002; Huacheng Yu (ICALP, 2021)

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. - Lijie Chen 001; Zhenjian Lu; Xin Lyu 002; Igor C. Oliveira 001 (ICALP, 2021)

On Distributed Differential Privacy and Counting Distinct Elements. - Lijie Chen 001; Badih Ghazi; Ravi Kumar 001; Pasin Manurangsi (ITCS, 2021)

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. - Shyan Akmal; Lijie Chen 001; Ce Jin 001; Malvika Raj; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2021)

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions. - Lijie Chen 001; Shuichi Hirahara; Neekon Vafa (Electron. Colloquium Comput. Complex., 2021)

Constructive Separations and Their Consequences. - Lijie Chen 001; Ce Jin 001; Rahul Santhanam; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2021)

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. - Lijie Chen 001; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena; Zhao Song 002; Huacheng Yu (Electron. Colloquium Comput. Complex., 2021)

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma. - Lijie Chen 001; Xin Lyu 002 (Electron. Colloquium Comput. Complex., 2021)

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. - Lijie Chen 001; Zhenjian Lu; Xin Lyu 002; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2021)

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. - Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2021)

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. - Lijie Chen 001; Ce Jin 001; R. Ryan Williams; Hongxun Wu (SODA, 2022)

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. - Lijie Chen 001; Gillat Kol; Dmitry Paramonov; Raghuvansh Saxena; Zhao Song 002; Huacheng Yu (Electron. Colloquium Comput. Complex., 2022)

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. - Lijie Chen 001; Jiatu Li; Tianqi Yang 001 (Electron. Colloquium Comput. Complex., 2022)

Unstructured Hardness to Average-Case Randomness. - Lijie Chen 001; Ron D. Rothblum; Roei Tell (Electron. Colloquium Comput. Complex., 2022)

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems. - Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2022)

New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method. - Lijie Chen 001 (Electron. Colloquium Comput. Complex., 2022)

Better Hardness via Algorithms, and New Forms of Hardness versus Randomness - Lijie Chen 001 (2022)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization. - Lijie Chen 001; Hanlin Ren (SIAM J. Comput., 2022)

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. - Lijie Chen 001; Xin Lyu 002; Avishay Tal; Hongxun Wu (ICALP, 2023)

Black-Box Constructive Proofs Are Unavoidable. - Lijie Chen 001; Ryan Williams 001; Tianqi Yang 001 (ITCS, 2023)

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. - Lijie Chen 001; William Hoza; Xin Lyu 002; Avishay Tal; Hongxun Wu (Electron. Colloquium Comput. Complex., 2023)

Symmetric Exponential Time Requires Near-Maximum Circuit Size. - Lijie Chen 001; Shuichi Hirahara; Hanlin Ren (Electron. Colloquium Comput. Complex., 2023)

Polynomial-Time Pseudodeterministic Construction of Primes. - Lijie Chen 001; Zhenjian Lu; Igor Carboni Oliveira; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2023)

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. - Lijie Chen 001; Roei Tell; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2023)

New ways of studying the BPP = P conjecture. - Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2023)

Guest Column: New ways of studying the BPP = P conjecture. - Lijie Chen 001; Roei Tell (SIGACT News, 2023)

Theoretical limitations of multi-layer Transformer. - Lijie Chen 001; Binghui Peng; Hongxun Wu (CoRR, 2024)

LatentQA: Teaching LLMs to Decode Activations Into Natural Language. - Alexander Pan; Lijie Chen 001; Jacob Steinhardt (CoRR, 2024)

Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin. - Lijie Chen 001; Jiatu Li; Jingxun Liang (Electron. Colloquium Comput. Complex., 2024)

Reverse Mathematics of Complexity Lower Bounds. - Lijie Chen 001; Jiatu Li; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic S12. - Lijie Chen 001; Jiatu Li; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2024)

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). - Lijie Chen 001; Ron D. Rothblum; Roei Tell (Electron. Colloquium Comput. Complex., 2024)

Quantum Merkle Trees. - Lijie Chen 001; Ramis Movassagh (Quantum, 2024)

Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs). - Marshall Ball; Lijie Chen 001; Roei Tell (Electron. Colloquium Comput. Complex., 2025)

Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associations. - Yiyou Sun; Yu Gai; Lijie Chen 001; Abhilasha Ravichander; Yejin Choi 001; Dawn Song (CoRR, 2025)

Understanding In-context Learning of Addition via Activation Subspaces. - Xinyan Hu; Kayo Yin; Michael I. Jordan; Jacob Steinhardt; Lijie Chen 001 (CoRR, 2025)