Lijie Chen
Massachusetts Institute of Technology
H-index: 21
North America-United States
Top articles of Lijie Chen
Title | Journal | Author(s) | Publication Date |
|---|---|---|---|
On the Unprovability of Circuit Size Bounds in Intuitionistic | arXiv preprint arXiv:2404.11841 | Lijie Chen Jiatu Li Igor C Oliveira | 2024/4/18 |
Nondeterministic Quasi-Polynomial Time is Average-Case Hard for Circuits | SIAM Journal on Computing | Lijie Chen | 2024/2/23 |
Constructive separations and their consequences | TheoretiCS | Lijie Chen Ce Jin Rahul Santhanam Ryan Williams | 2024/2/15 |
Polynomial-Time Pseudodeterministic Construction of Primes | Lijie Chen Zhenjian Lu Igor C Oliveira Hanlin Ren Rahul Santhanam | 2023/11/6 | |
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut | Lijie Chen Gillat Kol Dmitry Paramonov Raghuvansh R Saxena Zhao Song | 2023 | |
Symmetric Exponential Time Requires Near-Maximum Circuit Size | arXiv preprint arXiv:2309.12912 | Lijie Chen Shuichi Hirahara Hanlin Ren | 2023/9/22 |
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs | Lijie Chen Xin Lyu Avishay Tal Hongxun Wu | 2023 | |
Improved Merlin–Arthur protocols for central problems in fine-grained complexity | Algorithmica | Shyan Akmal Lijie Chen Ce Jin Malvika Raj Ryan Williams | 2023/8 |
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method | Lijie Chen | 2023 | |
Weighted pseudorandom generators via inverse analysis of random walks and shortcutting | Lijie Chen William M Hoza Xin Lyu Avishay Tal Hongxun Wu | 2023/11/6 | |
Guest Column: New ways of studying the BPP= P conjecture | ACM SIGACT News | Lijie Chen Roei Tell | 2023/6/14 |
Black-Box Constructive Proofs Are Unavoidable | Lijie Chen Ryan Williams Tianqi Yang | 2023 | |
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization | Lijie Chen Roei Tell Ryan Williams | 2023/11/6 | |
When arthur has neither random coins nor time to spare: Superfast derandomization of proof systems | Lijie Chen Roei Tell | 2023/6/2 | |
Average-case hardness of NP and PH from worst-case fine-grained assumptions | 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) | Lijie Chen Shuichi Hirahara Neekon Vafa | 2022/1 |
Beyond natural proofs: Hardness magnification and locality | ACM Journal of the ACM (JACM) | Lijie Chen Shuichi Hirahara Igor Carboni Oliveira Ján Pich Ninad Rajgopal | 2022/8/23 |
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions∗ | Lijie Chen Ce Jin R Ryan Williams Hongxun Wu | 2022 | |
Circuit Lower Bounds from Unconditional Derandomization of Restricted Merlin Arthur Protocols | Lijie Chen | 2022/3/21 | |
Efficient construction of rigid matrices using an NP oracle | SIAM Journal on Computing | Josh Alman Lijie Chen | 2022 |
Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise | Lijie Chen Roei Tell | 2022/2/7 |
Co-Authors
