| No. |
Title |
Author |
Year |
| 1 |
Black-Box Constructive Proofs Are Unavoidable |
Chen, Lijie et al. |
2023 |
| 2 |
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method |
Chen, Lijie |
2023 |
| 3 |
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs |
Chen, Lijie et al. |
2023 |
| 4 |
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions |
Chen, Lijie et al. |
2022 |
| 5 |
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs |
Chen, Lijie et al. |
2022 |
| 6 |
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity |
Akmal, Shyan et al. |
2022 |
| 7 |
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹ |
Chen, Lijie et al. |
2021 |
| 8 |
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs |
Chen, Lijie et al. |
2021 |
| 9 |
On Distributed Differential Privacy and Counting Distinct Elements |
Chen, Lijie et al. |
2021 |
| 10 |
Beyond Natural Proofs: Hardness Magnification and Locality |
Chen, Lijie et al. |
2020 |
| 11 |
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems |
Chen, Lijie et al. |
2019 |
| 12 |
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity |
Chen, Lijie et al. |
2019 |
| 13 |
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs |
Chen, Lijie et al. |
2018 |
| 14 |
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols |
Chen, Lijie et al. |
2018 |
| 15 |
Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures |
Chen, Lijie et al. |
2018 |
| 16 |
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product |
Chen, Lijie |
2018 |
| 17 |
Complexity-Theoretic Foundations of Quantum Supremacy Experiments |
Aaronson, Scott et al. |
2017 |
| 18 |
Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation |
Chen, Lijie |
2016 |
