Decidability and Shortest Strings in Formal Languages. - Levent Alpoge; Thomas Ang; Luke Schaeffer; Jeffrey O. Shallit (DCFS, 2011)

The Subword Complexity of k-Automatic Sequences is k-Synchronized - Daniel Goc; Luke Schaeffer; Jeffrey O. Shallit (CoRR, 2012)

An Improved Lower Bound for Stack Sorting - Luke Schaeffer (CoRR, 2012)

The Critical Exponent is Computable for Automatic Sequences. - Luke Schaeffer; Jeffrey O. Shallit (Int. J. Found. Comput. Sci., 2012)

Subword Complexity and k-Synchronization. - Daniel Goc; Luke Schaeffer; Jeffrey O. Shallit (Developments in Language Theory, 2013)

Ostrowski Numeration and the Local Period of Sturmian Words. - Luke Schaeffer (LATA, 2013)

Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance. - Chen Fei Du; Hamoon Mousavi; Luke Schaeffer; Jeffrey O. Shallit (CoRR, 2014)

A Physically Universal Cellular Automaton. - Luke Schaeffer (Electron. Colloquium Comput. Complex., 2014)

Avoiding Three Consecutive Blocks of the Same Size and Same Sum. - Julien Cassaigne; James D. Currie; Luke Schaeffer; Jeffrey O. Shallit (J. ACM, 2014)

A Physically Universal Quantum Cellular Automaton. - Luke Schaeffer (Automata, 2015)

A New Approach to the Paperfolding Sequences. - Daniel Goc; Hamoon Mousavi; Luke Schaeffer; Jeffrey O. Shallit (CiE, 2015)

Closed, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. - Luke Schaeffer; Jeffrey O. Shallit (CoRR, 2015)

The Classification of Reversible Bit Operations. - Scott Aaronson; Daniel Grier; Luke Schaeffer (Electron. Colloquium Comput. Complex., 2015)

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. - Stephen A. Fenner; Daniel Grier; Jochen Messner; Luke Schaeffer; Thomas Thierauf (Electron. Colloquium Comput. Complex., 2015)

Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. - Luke Schaeffer; Jeffrey O. Shallit (Electron. J. Comb., 2016)

The Classification of Stabilizer Operations over Qubits. - Daniel Grier; Luke Schaeffer (CoRR, 2016)

New Hardness Results for the Permanent Using Linear Optics. - Daniel Grier; Luke Schaeffer (Electron. Colloquium Comput. Complex., 2016)

Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties. - Chen Fei Du; Hamoon Mousavi; Luke Schaeffer; Jeffrey O. Shallit (Int. J. Found. Comput. Sci., 2016)

Decision algorithms for Fibonacci-automatic Words, I: Basic results. - Hamoon Mousavi; Luke Schaeffer; Jeffrey O. Shallit (RAIRO Theor. Informatics Appl., 2016)

Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability. - Chen Fei Du; Hamoon Mousavi; Eric Rowland; Luke Schaeffer; Jeffrey O. Shallit (Theor. Comput. Sci., 2017)

Interactive shallow Clifford circuits: quantum advantage against NC1 and beyond. - Daniel Grier; Luke Schaeffer (CoRR, 2019)

A Quantum Query Complexity Trichotomy for Regular Languages. - Scott Aaronson; Daniel Grier; Luke Schaeffer (Electron. Colloquium Comput. Complex., 2019)

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. - Adam Bene Watts; Robin Kothari; Luke Schaeffer; Avishay Tal (Electron. Colloquium Comput. Complex., 2019)

A Note on Key Agreement and Non-Interactive Commitments. - Alex Lombardi; Luke Schaeffer (IACR Cryptol. ePrint Arch., 2019)

Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. - Daniel Grier; Luke Schaeffer (STOC, 2020)

Interactive quantum advantage with noisy, shallow Clifford circuits. - Daniel Grier; Nathan Ju; Luke Schaeffer (CoRR, 2021)

Ostrowski-automatic sequences: Theory and applications. - Aseem R. Baranwal; Luke Schaeffer; Jeffrey O. Shallit (Theor. Comput. Sci., 2021)

The First-Order Theory of Binary Overlap-Free Words is Decidable. - Luke Schaeffer; Jeffrey O. Shallit (CoRR, 2022)

The Classification of Clifford Gates over Qubits. - Daniel Grier; Luke Schaeffer (Quantum, 2022)

On the Rational Degree of Boolean Functions and Applications. - Vishnu Iyer; Siddhartha Jain 004; Matt Kovacs-Deak; Vinayak M. Kumar; Luke Schaeffer; Daochen Wang; Michael Whitmeyer (Electron. Colloquium Comput. Complex., 2023)

Principal eigenstate classical shadows. - Daniel Grier; Hakop Pashayan; Luke Schaeffer (COLT, 2024)

Beatty Sequences for a Quadratic Irrational: Decidability and Applications. - Luke Schaeffer; Jeffrey O. Shallit; Stefan Zorcic (CoRR, 2024)

Decidability for Sturmian words. - Philipp Hieronymi; Dun Ma; Reed Oei; Luke Schaeffer; Christian Schulz 013; Jeffrey O. Shallit (Log. Methods Comput. Sci., 2024)

Sample-optimal classical shadows for pure states. - Daniel Grier; Hakop Pashayan; Luke Schaeffer (Quantum, 2024)

Trading T gates for dirty qubits in state preparation and unitary synthesis. - Guang Hao Low; Vadym Kliuchnikov; Luke Schaeffer (Quantum, 2024)

Fast simulation of planar Clifford circuits. - David Gosset; Daniel Grier; Alex Kerzner; Luke Schaeffer (Quantum, 2024)

Succinct Fermion Data Structures. - Joseph Carolan; Luke Schaeffer (ITCS, 2025)

Self-Verifying Predicates in Büchi Arithmetic. - Mazen Khodier; Luke Schaeffer; Jeffrey O. Shallit (CoRR, 2025)