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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI