Preprints and Publications - Google scholar
Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals With Daniel M Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu [arXiv]
Tight Bounds on Depth-2 QAC-circuits Computing Parity With Daniel Padé, Stephen Fenner, Thomas Thierauf [arXiv]
Streaming Quantum State Purification for General Mixed States With Debbie Leung, Zhi Li, Hakop Pashayan, and Luke Schaeffer [arXiv]
Quantum Threshold is Powerful With Jackson Morris TQC 2025 / CCC 2025 (Best Paper) [arXiv, slides, talk]
Improved Classical Shadows from Local Symmetries in the Schur Basis With Sihan Liu and Gaurav Mahajan [arXiv]
Principal Eigenstate Classical Shadows With Hakop Pashayan and Luke Schaeffer COLT 2024 [arXiv]
Complexity-theoretic foundations of BosonSampling with a linear number of modes With Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Felipe Hernández, and Michał Oszmaniec QIP 2024 / AQIS 2024 [arXiv]
Sample-Optimal Classical Shadows for Pure States With Hakop Pashayan and Luke Schaeffer TQC 2022 / Quantum 2024 [arXiv, slides]
The Complexity of Bipartite Gaussian Boson Sampling With Daniel J. Brod, Juan Miguel Arrazola, Marcos Benicio de Andrade Alonso, Nicolás Quesada QIP 2022 / Quantum 2022 [arXiv, slides, talk]
Classical Algorithms for Forrelation With Sergey Bravyi, David Gosset, Luke Schaeffer QIP 2022 / Theory of Computing 2024 [arXiv, talk]
Interactive Quantum Advantage with Noisy, Shallow Clifford Circuits With Nathan Ju, Luke Schaeffer QIP 2021 [arXiv]
Fast Simulation of Planar Clifford Circuits With David Gosset, Alex Kerzner, Luke Schaeffer QIP 2021 / Quantum 2024 [arXiv, software]
Interactive Shallow Clifford Circuits: Quantum Advantage Against NC^1 and Beyond With Luke Schaeffer QIP 2020 / STOC 2020 [arXiv, slides]
A Quantum Query Complexity Trichotomy for Regular Languages With Scott Aaronson and Luke Schaeffer QIP 2019 / FOCS 2019 [arXiv, slides, talk]
New Hardness Results for the Permanent Using Linear Optics With Luke Schaeffer CCC 2018 [arXiv, slides, talk]
The Classification of Clifford Gates over Qubits With Luke Schaeffer QIP 2018 / Quantum 2022 [arXiv, journal]
The Classification of Reversible Bit Operations With Scott Aaronson and Luke Schaeffer ITCS 2017 [arXiv, slides]
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems With Itai Arad, Adam Bouland, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang MFCS 2016 [arXiv]
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games With Stephen A. Fenner, Jochen Messner, Luke Schaeffer, and Thomas Thierauf ISAAC 2015 [ECCC, slides]
Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-complete ICALP 2013 [arXiv, slides]
On the Cyclic Van der Waerden Numbers Geombinatorics 2012 [pdf]