Publications (by Years)

Google Scholar Page

2023

  • New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method [eccc]
    Lijie Chen
    Innovations in Theoretical Computer Science (ITCS 2023)

  • Black-box Constructive Proofs are Unavoidable
    Lijie Chen, Ryan Williams, Tianqi Yang
    Innovations in Theoretical Computer Science (ITCS 2023)

  • Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut [eccc]
    Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

2022

  • Unstructured Hardness to Average-Case Randomness [eccc]
    Lijie Chen, Ron D. Rothblum, Roei Tell
    Foundations of Computer Science (FOCS 2022)

  • Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs [eccc]
    Lijie Chen, Jiatu Li, Tianqi Yang
    Computational Complexity Conference (CCC 2022)

  • Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity [eccc] [video by Ce at ITCS 2022]
    Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
    Innovations in Theoretical Computer Science (ITCS 2022)

  • Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions [eccc] [video by Neekon at ITCS 2022]
    Lijie Chen, Shuichi Hirahara, Neekon Vafa
    Innovations in Theoretical Computer Science (ITCS 2022)

  • Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions [arxiv]
    Lijie Chen, Ce Jin, Ryan Williams, Hongxun Wu
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)

2021

  • Constructive Separations and Their Consequences [eccc] [video by Ryan at FOCS 2021]
    Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
    Foundations of Computer Science (FOCS 2021)

  • Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise [eccc] [slides] [short summary]
    Lijie Chen, Roei Tell
    Foundations of Computer Science (FOCS 2021). Invited to the SICOMP Special Issue for FOCS 2021

  • Majority vs. Approximate Linear Sum and average-case complexity below NC1 [eccc] [slides by Igor] [video by Xin]
    Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Oliveira
    International Colloquium on Automata, Languages and Programming (ICALP), 2021

  • Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs [arxiv] [video by Raghuvansh]
    Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
    International Colloquium on Automata, Languages and Programming (ICALP), 2021

  • Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability [eccc]
    Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
    Symposium on the Theory of Computing (STOC 2021). Invited to the SICOMP Special Issue for STOC 2021

  • Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost [eccc] [Oded's choice] [slides]
    Lijie Chen, Roei Tell
    Symposium on the Theory of Computing (STOC 2021)

  • Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma [paper] [eccc]
    Lijie Chen, Xin Lyu
    Symposium on the Theory of Computing (STOC 2021)

  • On Distributed Differential Privacy and Counting Distinct Elements [arxiv] [long slides] [short slides] [summary]
    Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
    Innovations in Theoretical Computer Science (ITCS 2021)

2020

  • Almost Everywhere Circuit Lower Bounds from Non-Trivial Derandomization [eccc] [video by Xin Lyu at FOCS 2020] [slides by Ryan] [short highlight]
    Lijie Chen, Xin Lyu, Ryan Williams
    Foundations of Computer Science (FOCS 2020)

  • On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds [eccc] [video by Roei Tell in FOCS 2020]
    Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
    Foundations of Computer Science (FOCS 2020)

  • Sharp Threshold Results for Computational Complexity [eccc] [slides]
    Lijie Chen, Ce Jin, Ryan Williams
    Symposium on the Theory of Computing (STOC 2020)

2019

  • Efficient Construction of Rigid Matrices Using an NP Oracle [pdf] [slides] [Oded's choice]
    Josh Alman, Lijie Chen
    Foundations of Computer Science (FOCS 2019). Machtey Award for Best Student Paper. Invited to the SICOMP Special Issue for FOCS 2019

  • Hardness Magnification for all Sparse NP Languages [eccc]
    Lijie Chen, Ce Jin, Ryan Williams
    Foundations of Computer Science (FOCS 2019)

  • Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators [eccc]
    Lijie Chen, Ofer Grossman
    Symposium on Principles of Distributed Computing (PODC 2019)

  • Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity [slides] [proceeding version]
    Lijie Chen, Ryan Williams
    Computational Complexity Conference (CCC 2019). This paper subsumes a previous manuscript [arxiv]

  • Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds [eccc] [Oded's choice]
    Lijie Chen, Roei Tell
    Symposium on the Theory of Computing (STOC 2019). Danny Lewin Best Student Paper Award

  • Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols [arxiv] [slides]
    Lijie Chen, Ruosong Wang
    Innovations in Theoretical Computer Science (ITCS 2019)

2018

  • Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures [arxiv]
    Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, Yuancheng Yu
    Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

  • Improved Algorithms for Maintaining DFS Tree in Undirected Graphs [arxiv]
    Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang
    Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

  • On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product [eccc] [arxiv] [slides] [journal version] [short highlight]
    Lijie Chen
    Computational Complexity Conference (CCC 2018). Invited to the Toc Special Issue for CCC 2018

2017

  • On The Power of Statistical Zero Knowledge [eccc] [arxiv] [slides]
    Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan
    Foundations of Computer Science (FOCS 2017). Invited to the SICOMP Special Issue for FOCS 2017

  • Towards Instance Optimal Bounds for Best Arm Identification [arxiv] [conference version]
    Lijie Chen, Jian Li, Mingda Qiao
    Conference on Learning Theory (COLT 2017)

  • Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration [arxiv] [conference version]
    Lijie Chen, Anupam Gupta, Jian Li, Mingda Qiao and Ruosong Wang
    Conference on Learning Theory (COLT 2017)

  • Complexity-Theoretic Foundations of Quantum Supremacy Experiments [eccc] [arxiv] [slides]
    Scott Aaronson, Lijie Chen
    Computational Complexity Conference (CCC 2017). Invited to the Toc Special Issue for CCC 2017

  • Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection [arxiv] [conference version]
    Lijie Chen, Jian Li, Mingda Qiao
    International Conference on Artificial Intelligence and Statistics (AISTATS 2017)

  • K-Memory Strategies in Repeated Games
    Lijie Chen, Fangzhen Lin, Pingzhong Tang, Kangning Wang, Ruosong Wang, Shiheng Wang
    Extended abstract, International Conference on Antonomous Agents and Multiagent Sytems (AAMAS 2017)

  • Bounded rationality of restricted Turing machines [conference version]
    Lijie Chen, Pingzhong Tang, Ruosong Wang
    AAAI 2017

2016

  • Pure Exploration of Multi-armed Bandit Under Matroid Constraints [arxiv] [conference version] [slides]
    Lijie Chen, Anupum Gupta, Jian Li
    Conference on Learning Theory (COLT 2016)

  • Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture [arxiv] [conference version] [slides]
    Lijie Chen, Jian Li
    Conference on Learning Theory Open Problem (COLT 2016 Open Problem)

Notes

  • A Note on Oracle Separations for BQP
    Lijie Chen
    [arxiv]

Old Manuscripts

  • On the Optimal Sample Complexity for Best Arm Identification
    Lijie Chen, Jian Li
    [arxiv]