Lijie Chen

ORCID

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 119

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

FOCS

STOC

Publications

Lijie Chen, Jiatu Li, Igor C. Oliveira
. CoRR (2024)
Lijie Chen, Shuichi Hirahara, Hanlin Ren
Symmetric Exponential Time Requires Near-Maximum Circuit Size. STOC (2024)
Lijie Chen, Jiatu Li, Igor Carboni Oliveira
Reverse Mathematics of Complexity Lower Bounds. Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, Jiatu Li, Igor Carboni Oliveira
. Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. TheoretiCS 3 (2024)
Lijie Chen, Ron D. Rothblum, Roei Tell
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. FOCS (2023)
Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds. J. ACM 70 (4) (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Shuichi Hirahara, Hanlin Ren
Symmetric Exponential Time Requires Near-Maximum Circuit Size. CoRR (2023)
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. FOCS (2023)
Lijie Chen, Shuichi Hirahara, Hanlin Ren
Symmetric Exponential Time Requires Near-Maximum Circuit Size. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. CoRR (2023)
Lijie Chen, Roei Tell
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems. STOC (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. SODA (2023)
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. ITCS (2023)
Lijie Chen, Roei Tell
New ways of studying the BPP = P conjecture. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Roei Tell
Guest Column: New ways of studying the BPP = P conjecture. SIGACT News 54 (2) (2023)
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, R. Ryan Williams
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Algorithmica 85 (8) (2023)
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. ICALP (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS (2023)
Lijie Chen, Ryan Williams, Tianqi Yang
Black-Box Constructive Proofs Are Unavoidable. ITCS (2023)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. SODA (2022)
Lijie Chen, Shuichi Hirahara, Neekon Vafa
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. ITCS (2022)
Lijie Chen, Roei Tell
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Ron D. Rothblum, Roei Tell
Unstructured Hardness to Average-Case Randomness. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. FOCS (2022)
Lijie Chen, Ron D. Rothblum, Roei Tell
Unstructured Hardness to Average-Case Randomness. FOCS (2022)
Lijie Chen, Jiatu Li, Tianqi Yang
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Hanlin Ren
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization. SIAM J. Comput. 51 (3) (2022)
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. ITCS (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. CoRR (2022)
Lijie Chen, Jiatu Li, Tianqi Yang
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. CCC (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2022)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. J. ACM 69 (4) (2022)
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. CoRR (2021)
Lijie Chen, Ramis Movassagh
Quantum Merkle Trees. CoRR (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. ICALP (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. ICALP (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
On Distributed Differential Privacy and Counting Distinct Elements. ITCS (2021)
Lijie Chen, Roei Tell
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. STOC (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR (2021)
Lijie Chen, Xin Lyu
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. STOC (2021)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Shuichi Hirahara, Neekon Vafa
Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. FOCS (2021)
Lijie Chen, Xin Lyu
Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma. Electron. Colloquium Comput. Complex. 28 (2021)
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
Almost optimal super-constant-pass streaming lower bounds for reachability. STOC (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. Electron. Colloquium Comput. Complex. 28 (2021)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On the Power of Statistical Zero Knowledge. SIAM J. Comput. 49 (4) (2020)
Lijie Chen, Xin Lyu, R. Ryan Williams
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. FOCS (2020)
Lijie Chen, Xin Lyu, Ryan Williams
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. Electron. Colloquium Comput. Complex. 27 (2020)
Lijie Chen, Hanlin Ren
Strong average-case lower bounds from non-trivial derandomization. STOC (2020)
Lijie Chen, Ce Jin, R. Ryan Williams
Sharp threshold results for computational complexity. STOC (2020)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. ITCS (2020)
Lijie Chen, Ce Jin, R. Ryan Williams
Sharp Threshold Results for Computational Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. FOCS (2020)
Lijie Chen, Hanlin Ren
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. Electron. Colloquium Comput. Complex. 27 (2020)
Lijie Chen
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Theory Comput. 16 (2020)
Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
On Distributed Differential Privacy and Counting Distinct Elements. CoRR (2020)
Lijie Chen, Roei Tell
Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. Electron. Colloquium Comput. Complex. 27 (2020)
Lijie Chen, Ryan Williams
An Equivalence Class for Orthogonal Vectors. SODA (2019)
Lijie Chen, Ce Jin, R. Ryan Williams
Hardness Magnification for all Sparse NP Languages. FOCS (2019)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. CoRR (2019)
Lijie Chen, Ofer Grossman
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators. CoRR (2019)
Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Electron. Colloquium Comput. Complex. 26 (2019)
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds. Electron. Colloquium Comput. Complex. 26 (2019)
Lijie Chen
Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. FOCS (2019)
Lijie Chen, R. Ryan Williams
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. Computational Complexity Conference (2019)
Lijie Chen, Roei Tell
Bootstrapping results for threshold circuits "just beyond" known lower bounds. STOC (2019)
Josh Alman, Lijie Chen
Efficient Construction of Rigid Matrices Using an NP Oracle. FOCS (2019)
Lijie Chen
Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Computational Complexity Conference (2019)
Lijie Chen, Ce Jin, Ryan Williams
Hardness Magnification for all Sparse NP Languages. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. Electron. Colloquium Comput. Complex. 26 (2019)
Lijie Chen, Ruosong Wang
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. ITCS (2019)
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
Fine-grained Complexity Meets IP = PSPACE. SODA (2019)
Lijie Chen, Ofer Grossman
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators. PODC (2019)
Lijie Chen, Ofer Grossman
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators. Electron. Colloquium Comput. Complex. 26 (2019)
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
Fine-grained Complexity Meets IP = PSPACE. CoRR (2018)
Lijie Chen
Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits. CoRR (2018)
Lijie Chen
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. CoRR (2018)
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. SWAT (2018)
Lijie Chen, Ruosong Wang
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. CoRR (2018)
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. SWAT (2018)
Lijie Chen, Roei Tell
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures. CoRR (2018)
Lijie Chen
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Electron. Colloquium Comput. Complex. 25 (2018)
Lijie Chen, Ryan Williams
An Equivalence Class for Orthogonal Vectors. CoRR (2018)
Lijie Chen
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Computational Complexity Conference (2018)
Lijie Chen, Jian Li, Mingda Qiao
Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection. CoRR (2017)
Lijie Chen, Jian Li, Mingda Qiao
Towards Instance Optimal Bounds for Best Arm Identification. COLT (2017)
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
On the Power of Statistical Zero Knowledge. FOCS (2017)

Lijie Chen.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Lijie Chen