Preprints and Publications

Sample-Optimal Classical Shadows for Pure States With Hakop Pashayan and Luke Schaeffer TQC 2022 [arXiv]
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 [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 [arXiv]
Depth-2 QAC Circuits Cannot Simulate Quantum Parity With Daniel Padé, Stephen Fenner, Thomas Thierauf [arXiv]
Interactive Shallow Clifford Circuits: Quantum Advantage Against NC^1 and Beyond With Luke Schaeffer QIP 2020 / STOC 2020 [arXiv, slides, talk]
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]