Lijie Chen

Abhilasha Ravichander

Yejin Choi

Dawn Song

CoRR, April, 2025

Nondeterministic Quasi-Polynomial Time is Average-Case Hard for $\textsf{ACC}$ Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2025

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$.

[BibT_eX]

[DOI]

Igor C. Oliveira

Log. Methods Comput. Sci., 2025

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?).

[BibT_eX]

[DOI]

Ron D. Rothblum

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin.

[BibT_eX]

[DOI]

Jingxun Liang

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Towards Free Lunch Derandomization from Necessary Assumptions (And OWFs).

[BibT_eX]

[DOI]

Marshall Ball

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Quantum Merkle Trees.

[BibT_eX]

[DOI]

Ramis Movassagh

Quantum, 2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S<sup>1</sup><sub>2</sub>.

[BibT_eX]

[DOI]

Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

LatentQA: Teaching LLMs to Decode Activations Into Natural Language.

[BibT_eX]

[DOI]

Alexander Pan

Jacob Steinhardt

CoRR, 2024

Theoretical limitations of multi-layer Transformer.

[BibT_eX]

[DOI]

Binghui Peng

Hongxun Wu

CoRR, 2024

Symmetric Exponential Time Requires Near-Maximum Circuit Size.

[BibT_eX]

[DOI]

Shuichi Hirahara

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Reverse Mathematics of Complexity Lower Bounds.

[BibT_eX]

[DOI]

Igor C. Oliveira

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Guest Column: New ways of studying the BPP = P conjecture.

[BibT_eX]

[DOI]

SIGACT News, 2023

New ways of studying the BPP = P conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Black-Box Constructive Proofs Are Unavoidable.

[BibT_eX]

[DOI]

Ryan Williams

Tianqi Yang

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.

[BibT_eX]

[DOI]

Ryan Williams

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization.

[BibT_eX]

[DOI]

SIAM J. Comput., June, 2022

Better Hardness via Algorithms, and New Forms of Hardness versus Randomness

[BibT_eX]

[DOI]

PhD thesis, 2022

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions.

[BibT_eX]

[DOI]

Shuichi Hirahara

Neekon Vafa

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Unstructured Hardness to Average-Case Randomness.

[BibT_eX]

[DOI]

Ron D. Rothblum

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.

[BibT_eX]

[DOI]

Tianqi Yang

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.

[BibT_eX]

[DOI]

Zhenjian Lu

Xin Lyu

Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma.

[BibT_eX]

[DOI]

Xin Lyu

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Almost optimal super-constant-pass streaming lower bounds for reachability.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

On Distributed Differential Privacy and Counting Distinct Elements.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Constructive Separations and Their Consequences.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Strong average-case lower bounds from non-trivial derandomization.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Sharp threshold results for computational complexity.

[BibT_eX]

[DOI]

Ce Jin

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Beyond Natural Proofs: Hardness Magnification and Locality.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization.

[BibT_eX]

[DOI]

Xin Lyu

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Bootstrapping results for threshold circuits "just beyond" known lower bounds.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

An Equivalence Class for Orthogonal Vectors.

[BibT_eX]

[DOI]

Ryan Williams

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fine-grained Complexity Meets IP = PSPACE.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators.

[BibT_eX]

[DOI]

Ofer Grossman

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols.

[BibT_eX]

[DOI]

Ruosong Wang

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Hardness Magnification for all Sparse NP Languages.

[BibT_eX]

[DOI]

Ce Jin

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Construction of Rigid Matrices Using an NP Oracle.

[BibT_eX]

[DOI]

Josh Alman

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.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

CoRR, 2018

An Improved Algorithm for Incremental DFS Tree in Undirected Graphs.

[BibT_eX]

[DOI]

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Erik D. Demaine

Yuzhou Gu

Yinzhan Xu

Yuancheng Yu

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

On the Power of Statistical Zero Knowledge.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Towards Instance Optimal Bounds for Best Arm Identification.

[BibT_eX]

[DOI]

Mingda Qiao

Proceedings of the 30th Conference on Learning Theory, 2017

Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

Complexity-Theoretic Foundations of Quantum Supremacy Experiments.

[BibT_eX]

[DOI]

Scott Aaronson

Proceedings of the 32nd Computational Complexity Conference, 2017

K-Memory Strategies in Repeated Games.

[BibT_eX]

[DOI]

Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, 2017

Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection.

[BibT_eX]

[DOI]

Mingda Qiao

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

Bounded Rationality of Restricted Turing Machines.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Pingzhong Tang

Ruosong Wang

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

On SZK and PP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Improved Algorithms for Maintaining DFS Tree in Undirected Graphs.

[BibT_eX]

[DOI]

CoRR, 2016

Adaptivity vs Postselection.

[BibT_eX]

[DOI]

CoRR, 2016

A Note on Oracle Separations for BQP.

[BibT_eX]

[DOI]

CoRR, 2016

Adaptivity vs. Postselection, and Hardness Amplification for Polynomial Approximation.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

Pure Exploration of Multi-armed Bandit Under Matroid Constraints.

[BibT_eX]

[DOI]

Anupam Gupta

Proceedings of the 29th Conference on Learning Theory, 2016

2015

On the Optimal Sample Complexity for Best Arm Identification.

[BibT_eX]

[DOI]

CoRR, 2015

Bounded Rationality of Restricted Turing Machines.

[BibT_eX]

[DOI]