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 |