Luke Schaeffer

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 33

Top Topics

Cellular Automaton

Query Complexity

Regular Languages

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Daniel Grier, Hakop Pashayan, Luke Schaeffer
Principal eigenstate classical shadows. CoRR (2024)
Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
Decidability for Sturmian words. Log. Methods Comput. Sci. 20 (3) (2024)
David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer
Fast simulation of planar Clifford circuits. Quantum 8 (2024)
Daniel Grier, Hakop Pashayan, Luke Schaeffer
Principal eigenstate classical shadows. COLT (2024)
Luke Schaeffer, Jeffrey O. Shallit, Stefan Zorcic
Beatty Sequences for a Quadratic Irrational: Decidability and Applications. CoRR (2024)
Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer
On the Rational Degree of Boolean Functions and Applications. Electron. Colloquium Comput. Complex. (2023)
Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer
On the Rational Degree of Boolean Functions and Applications. CoRR (2023)
Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
Decidability for Sturmian Words. CSL (2022)
Daniel Grier, Luke Schaeffer
The Classification of Clifford Gates over Qubits. Quantum 6 (2022)
Luke Schaeffer, Jeffrey O. Shallit
The First-Order Theory of Binary Overlap-Free Words is Decidable. CoRR (2022)
Daniel Grier, Hakop Pashayan, Luke Schaeffer
Sample-optimal classical shadows for pure states. CoRR (2022)
Daniel Grier, Nathan Ju, Luke Schaeffer
Interactive quantum advantage with noisy, shallow Clifford circuits. CoRR (2021)
Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
Decidability for Sturmian words. CoRR (2021)
Aseem R. Baranwal, Luke Schaeffer, Jeffrey O. Shallit
Ostrowski-automatic sequences: Theory and applications. Theor. Comput. Sci. 858 (2021)
David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer
Fast simulation of planar Clifford circuits. CoRR (2020)
Daniel Grier, Luke Schaeffer
Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. STOC (2020)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC (2019)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. Electron. Colloquium Comput. Complex. 26 (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR (2019)
Daniel Grier, Luke Schaeffer
and beyond. CoRR (2019)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. FOCS (2019)
Alex Lombardi, Luke Schaeffer
A Note on Key Agreement and Non-Interactive Commitments. IACR Cryptol. ePrint Arch. 2019 (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Daniel Grier, Luke Schaeffer
New Hardness Results for the Permanent Using Linear Optics. Computational Complexity Conference (2018)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. CoRR (2018)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. ITCS (2017)
Chen Fei Du, Hamoon Mousavi, Eric Rowland, Luke Schaeffer, Jeffrey O. Shallit
Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability. Theor. Comput. Sci. 657 (2017)
Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
Decision algorithms for Fibonacci-automatic Words, I: Basic results. RAIRO Theor. Informatics Appl. 50 (1) (2016)
Daniel Grier, Luke Schaeffer
New Hardness Results for the Permanent Using Linear Optics. Electron. Colloquium Comput. Complex. 23 (2016)
Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties. Int. J. Found. Comput. Sci. 27 (8) (2016)
Luke Schaeffer, Jeffrey O. Shallit
Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. Electron. J. Comb. 23 (1) (2016)
Daniel Grier, Luke Schaeffer
New Hardness Results for the Permanent Using Linear Optics. CoRR (2016)
Daniel Grier, Luke Schaeffer
The Classification of Stabilizer Operations over Qubits. CoRR (2016)
Luke Schaeffer, Jeffrey O. Shallit
Closed, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. CoRR (2015)
Luke Schaeffer
A Physically Universal Cellular Automaton. ITCS (2015)
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. ISAAC (2015)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. Electron. Colloquium Comput. Complex. 22 (2015)
Luke Schaeffer
A Physically Universal Quantum Cellular Automaton. Automata (2015)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. CoRR (2015)
Daniel Goc, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
A New Approach to the Paperfolding Sequences. CiE (2015)
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. Electron. Colloquium Comput. Complex. 22 (2015)
Luke Schaeffer
A Physically Universal Cellular Automaton. Electron. Colloquium Comput. Complex. 21 (2014)
Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey O. Shallit
Avoiding Three Consecutive Blocks of the Same Size and Same Sum. J. ACM 61 (2) (2014)
Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance. CoRR (2014)
Luke Schaeffer
Ostrowski Numeration and the Local Period of Sturmian Words. LATA (2013)
Daniel Goc, Luke Schaeffer, Jeffrey O. Shallit
Subword Complexity and k-Synchronization. Developments in Language Theory (2013)
Luke Schaeffer, Jeffrey O. Shallit
The Critical Exponent is Computable for Automatic Sequences. Int. J. Found. Comput. Sci. 23 (8) (2012)
Daniel Goc, Luke Schaeffer, Jeffrey O. Shallit
The Subword Complexity of k-Automatic Sequences is k-Synchronized CoRR (2012)
Luke Schaeffer
An Improved Lower Bound for Stack Sorting CoRR (2012)
Luke Schaeffer
Ostrowski Numeration and the Local Period of Sturmian Words CoRR (2012)
Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey O. Shallit
Avoiding Three Consecutive Blocks of the Same Size and Same Sum CoRR (2011)
Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit
Decidability and Shortest Strings in Formal Languages CoRR (2011)
Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit
Decidability and Shortest Strings in Formal Languages. DCFS (2011)