Lijie Chen

According to our database, Lijie Chen authored at least 68 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?).

Lijie Chen, Ron D. Rothblum, Roei Tell

Electron. Colloquium Comput. Complex., 2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S¹₂.

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

Reverse Mathematics of Complexity Lower Bounds.

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

2023

Guest Column: New ways of studying the BPP = P conjecture.

Lijie Chen, Roei Tell

SIGACT News, 2023

New ways of studying the BPP = P conjecture.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2023

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.

Lijie Chen, Roei Tell, Ryan Williams

Electron. Colloquium Comput. Complex., 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2023

Symmetric Exponential Time Requires Near-Maximum Circuit Size.

Lijie Chen, Shuichi Hirahara, Hanlin Ren

Electron. Colloquium Comput. Complex., 2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

Electron. Colloquium Comput. Complex., 2023

New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method.

Lijie Chen

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Black-Box Constructive Proofs Are Unavoidable.

Lijie Chen, Ryan Williams, Tianqi Yang

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.

Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization.

Lijie Chen, Hanlin Ren

SIAM J. Comput., June, 2022

Better Hardness via Algorithms, and New Forms of Hardness versus Randomness

Lijie Chen

PhD thesis, 2022

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2022

Unstructured Hardness to Average-Case Randomness.

Lijie Chen, Ron D. Rothblum, Roei Tell

Electron. Colloquium Comput. Complex., 2022

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.

Lijie Chen, Jiatu Li, Tianqi Yang

Electron. Colloquium Comput. Complex., 2022

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Electron. Colloquium Comput. Complex., 2022

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions.

Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma.

Lijie Chen, Xin Lyu

Electron. Colloquium Comput. Complex., 2021

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Electron. Colloquium Comput. Complex., 2021

Constructive Separations and Their Consequences.

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

Electron. Colloquium Comput. Complex., 2021

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions.

Lijie Chen, Shuichi Hirahara, Neekon Vafa

Electron. Colloquium Comput. Complex., 2021

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity.

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

Electron. Colloquium Comput. Complex., 2021

Quantum Merkle Trees.

Lijie Chen, Ramis Movassagh

CoRR, 2021

On Distributed Differential Privacy and Counting Distinct Elements.

Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

On the Power of Statistical Zero Knowledge.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

SIAM J. Comput., 2020

Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2020

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization.

Lijie Chen, Hanlin Ren

Electron. Colloquium Comput. Complex., 2020

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.

Lijie Chen, Xin Lyu, Ryan Williams

Electron. Colloquium Comput. Complex., 2020

Sharp Threshold Results for Computational Complexity.

Lijie Chen, Ce Jin, R. Ryan Williams

Electron. Colloquium Comput. Complex., 2020

Strong average-case lower bounds from non-trivial derandomization.

Lijie Chen, Hanlin Ren

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.

Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Beyond Natural Proofs: Hardness Magnification and Locality.

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2019

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds.

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

Electron. Colloquium Comput. Complex., 2019

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems.

Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams

Electron. Colloquium Comput. Complex., 2019

Hardness Magnification for all Sparse NP Languages.

Lijie Chen, Ce Jin, Ryan Williams

Electron. Colloquium Comput. Complex., 2019

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators.

Lijie Chen, Ofer Grossman

Electron. Colloquium Comput. Complex., 2019

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits.

Lijie Chen

Electron. Colloquium Comput. Complex., 2019

An Equivalence Class for Orthogonal Vectors.

Lijie Chen, Ryan Williams

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fine-grained Complexity Meets IP = PSPACE.

Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols.

Lijie Chen, Ruosong Wang

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Efficient Construction of Rigid Matrices Using an NP Oracle.

Josh Alman, Lijie Chen

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity.

Lijie Chen, R. Ryan Williams

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2018

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product.

Lijie Chen

Electron. Colloquium Comput. Complex., 2018

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

Lijie Chen

CoRR, 2018

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs.

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 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

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

2017

Towards Instance Optimal Bounds for Best Arm Identification.

Lijie Chen, Jian Li, Mingda Qiao

Proceedings of the 30th Conference on Learning Theory, 2017

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.

Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao, Ruosong Wang

Proceedings of the 30th Conference on Learning Theory, 2017

K-Memory Strategies in Repeated Games.

Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang

Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection.

Lijie Chen, Jian Li, Mingda Qiao

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

Bounded Rationality of Restricted Turing Machines.

Lijie Chen, Pingzhong Tang, Ruosong Wang

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

On SZK and PP.

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

Electron. Colloquium Comput. Complex., 2016

Complexity-Theoretic Foundations of Quantum Supremacy Experiments.

Scott Aaronson, Lijie Chen

Electron. Colloquium Comput. Complex., 2016

Improved Algorithms for Maintaining DFS Tree in Undirected Graphs.

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang

CoRR, 2016

Adaptivity vs Postselection.

Lijie Chen

CoRR, 2016

A Note on Oracle Separations for BQP.

Lijie Chen

CoRR, 2016

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation.

Lijie Chen

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture.

Lijie Chen, Jian Li

Proceedings of the 29th Conference on Learning Theory, 2016

Pure Exploration of Multi-armed Bandit Under Matroid Constraints.

Lijie Chen, Anupam Gupta, Jian Li

Proceedings of the 29th Conference on Learning Theory, 2016

2015

On the Optimal Sample Complexity for Best Arm Identification.

Lijie Chen, Jian Li

CoRR, 2015

Bounded Rationality of Restricted Turing Machines.

Lijie Chen, Pingzhong Tang

Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015