Lijie Chen

Orcid: 0000-0002-6084-4729

Affiliations:
  • University of California, Berkeley, CA, USA
  • Massachusetts Institute of Technolog, Cambridge, MA, USA (former)


According to our database1, Lijie Chen authored at least 68 papers between 2015 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?).
Electron. Colloquium Comput. Complex., 2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S<sup>1</sup><sub>2</sub>.
Electron. Colloquium Comput. Complex., 2024

Reverse Mathematics of Complexity Lower Bounds.
Electron. Colloquium Comput. Complex., 2024

2023
Guest Column: New ways of studying the BPP = P conjecture.
SIGACT News, 2023

New ways of studying the BPP = P conjecture.
Electron. Colloquium Comput. Complex., 2023

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.
Electron. Colloquium Comput. Complex., 2023

Polynomial-Time Pseudodeterministic Construction of Primes.
Electron. Colloquium Comput. Complex., 2023

Symmetric Exponential Time Requires Near-Maximum Circuit Size.
Electron. Colloquium Comput. Complex., 2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.
Electron. Colloquium Comput. Complex., 2023

New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Black-Box Constructive Proofs Are Unavoidable.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization.
SIAM J. Comput., June, 2022

Better Hardness via Algorithms, and New Forms of Hardness versus Randomness
PhD thesis, 2022

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.
Electron. Colloquium Comput. Complex., 2022

Unstructured Hardness to Average-Case Randomness.
Electron. Colloquium Comput. Complex., 2022

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.
Electron. Colloquium Comput. Complex., 2022

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.
Electron. Colloquium Comput. Complex., 2022

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise.
Electron. Colloquium Comput. Complex., 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.
Electron. Colloquium Comput. Complex., 2021

Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma.
Electron. Colloquium Comput. Complex., 2021

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.
Electron. Colloquium Comput. Complex., 2021

Constructive Separations and Their Consequences.
Electron. Colloquium Comput. Complex., 2021

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions.
Electron. Colloquium Comput. Complex., 2021

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity.
Electron. Colloquium Comput. Complex., 2021

Quantum Merkle Trees.
CoRR, 2021

On Distributed Differential Privacy and Counting Distinct Elements.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020
On the Power of Statistical Zero Knowledge.
SIAM J. Comput., 2020

Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost.
Electron. Colloquium Comput. Complex., 2020

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization.
Electron. Colloquium Comput. Complex., 2020

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.
Electron. Colloquium Comput. Complex., 2020

Sharp Threshold Results for Computational Complexity.
Electron. Colloquium Comput. Complex., 2020

Strong average-case lower bounds from non-trivial derandomization.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Beyond Natural Proofs: Hardness Magnification and Locality.
Electron. Colloquium Comput. Complex., 2019

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds.
Electron. Colloquium Comput. Complex., 2019

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems.
Electron. Colloquium Comput. Complex., 2019

Hardness Magnification for all Sparse NP Languages.
Electron. Colloquium Comput. Complex., 2019

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators.
Electron. Colloquium Comput. Complex., 2019

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits.
Electron. Colloquium Comput. Complex., 2019

An Equivalence Class for Orthogonal Vectors.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fine-grained Complexity Meets IP = PSPACE.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Efficient Construction of Rigid Matrices Using an NP Oracle.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity.
Proceedings of the 34th Computational Complexity Conference, 2019

2018
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds.
Electron. Colloquium Comput. Complex., 2018

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product.
Electron. Colloquium Comput. Complex., 2018

Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits.
CoRR, 2018

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

2017
Towards Instance Optimal Bounds for Best Arm Identification.
Proceedings of the 30th Conference on Learning Theory, 2017

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.
Proceedings of the 30th Conference on Learning Theory, 2017

K-Memory Strategies in Repeated Games.
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection.
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

Bounded Rationality of Restricted Turing Machines.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
On SZK and PP.
Electron. Colloquium Comput. Complex., 2016

Complexity-Theoretic Foundations of Quantum Supremacy Experiments.
Electron. Colloquium Comput. Complex., 2016

Improved Algorithms for Maintaining DFS Tree in Undirected Graphs.
CoRR, 2016

Adaptivity vs Postselection.
CoRR, 2016

A Note on Oracle Separations for BQP.
CoRR, 2016

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture.
Proceedings of the 29th Conference on Learning Theory, 2016

Pure Exploration of Multi-armed Bandit Under Matroid Constraints.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
On the Optimal Sample Complexity for Best Arm Identification.
CoRR, 2015

Bounded Rationality of Restricted Turing Machines.
Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015


  Loading...