Luke Schaeffer

60 papers A* 4A 4B 2C 4Journal 44Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Beatty sequences for a quadratic irrational: Decidability and applications. Discret. Math. Luke Schaeffer, Jeffrey O. Shallit, Stefan Zorcic
2026	J	`jnl`	On Error Thresholds for Pauli Channels: Some answers with many more questions. CoRR Avantika Agarwal, Alan Bu, Amolak Ratan Kalra, Debbie W. Leung, Luke Schaeffer, Graeme Smith
2025	J	`jnl`	Self-Verifying Predicates in Büchi Arithmetic. CoRR Mazen Khodier, Luke Schaeffer, Jeffrey O. Shallit
2025	C	`conf`	Self-verifying Predicates in Büchi Arithmetic. CIAA Mazen Khodier, Luke Schaeffer, Jeffrey O. Shallit
2025	A	`conf`	Succinct Fermion Data Structures. ITCS Joseph Carolan, Luke Schaeffer
2024	J	`jnl`	Beatty Sequences for a Quadratic Irrational: Decidability and Applications. CoRR Luke Schaeffer, Jeffrey O. Shallit, Stefan Zorcic
2024	J	`jnl`	Decidability for Sturmian words. Log. Methods Comput. Sci. Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
2024	J	`jnl`	Fast simulation of planar Clifford circuits. Quantum David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer
2024	A*	`conf`	Principal eigenstate classical shadows. COLT Daniel Grier, Hakop Pashayan, Luke Schaeffer
2024	J	`jnl`	Principal eigenstate classical shadows. CoRR Daniel Grier, Hakop Pashayan, Luke Schaeffer
2024	J	`jnl`	Sample-optimal classical shadows for pure states. Quantum Daniel Grier, Hakop Pashayan, Luke Schaeffer
2024	J	`jnl`	Trading T gates for dirty qubits in state preparation and unitary synthesis. Quantum Guang Hao Low, Vadym Kliuchnikov, Luke Schaeffer
2023	J	`jnl`	On the Rational Degree of Boolean Functions and Applications. CoRR Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer
2023	J	`jnl`	On the Rational Degree of Boolean Functions and Applications. Electron. Colloquium Comput. Complex. Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer
2022	B	`conf`	Decidability for Sturmian Words. CSL Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
2022	J	`jnl`	Sample-optimal classical shadows for pure states. CoRR Daniel Grier, Hakop Pashayan, Luke Schaeffer
2022	J	`jnl`	The Classification of Clifford Gates over Qubits. Quantum Daniel Grier, Luke Schaeffer
2022	J	`jnl`	The First-Order Theory of Binary Overlap-Free Words is Decidable. CoRR Luke Schaeffer, Jeffrey O. Shallit
2021	J	`jnl`	Decidability for Sturmian words. CoRR Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, Jeffrey O. Shallit
2021	J	`jnl`	Interactive quantum advantage with noisy, shallow Clifford circuits. CoRR Daniel Grier, Nathan Ju, Luke Schaeffer
2021	J	`jnl`	Ostrowski-automatic sequences: Theory and applications. Theor. Comput. Sci. Aseem R. Baranwal, Luke Schaeffer, Jeffrey O. Shallit
2020	J	`jnl`	Fast simulation of planar Clifford circuits. CoRR David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer
2020	A*	`conf`	Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond. STOC Daniel Grier, Luke Schaeffer
2019	J	`jnl`	A Note on Key Agreement and Non-Interactive Commitments. IACR Cryptol. ePrint Arch. Alex Lombardi, Luke Schaeffer
2019	A*	`conf`	A Quantum Query Complexity Trichotomy for Regular Languages. FOCS Scott Aaronson, Daniel Grier, Luke Schaeffer
2019	J	`jnl`	A Quantum Query Complexity Trichotomy for Regular Languages. Electron. Colloquium Comput. Complex. Scott Aaronson, Daniel Grier, Luke Schaeffer
2019	A*	`conf`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	J	`jnl`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	J	`jnl`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	J	`jnl`	Interactive shallow Clifford circuits: quantum advantage against NC CoRR Daniel Grier, Luke Schaeffer
2018	J	`jnl`	A Quantum Query Complexity Trichotomy for Regular Languages. CoRR Scott Aaronson, Daniel Grier, Luke Schaeffer
2018	A	`conf`	New Hardness Results for the Permanent Using Linear Optics. CCC Daniel Grier, Luke Schaeffer
2017	J	`jnl`	Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability. Theor. Comput. Sci. Chen Fei Du, Hamoon Mousavi, Eric Rowland, Luke Schaeffer, Jeffrey O. Shallit
2017	A	`conf`	The Classification of Reversible Bit Operations. ITCS Scott Aaronson, Daniel Grier, Luke Schaeffer
2016	J	`jnl`	Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. Electron. J. Comb. Luke Schaeffer, Jeffrey O. Shallit
2016	J	`jnl`	Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties. Int. J. Found. Comput. Sci. Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
2016	J	`jnl`	Decision algorithms for Fibonacci-automatic Words, I: Basic results. RAIRO Theor. Informatics Appl. Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
2016	J	`jnl`	New Hardness Results for the Permanent Using Linear Optics. CoRR Daniel Grier, Luke Schaeffer
2016	J	`jnl`	New Hardness Results for the Permanent Using Linear Optics. Electron. Colloquium Comput. Complex. Daniel Grier, Luke Schaeffer
2016	J	`jnl`	The Classification of Stabilizer Operations over Qubits. CoRR Daniel Grier, Luke Schaeffer
2015	C	`conf`	A New Approach to the Paperfolding Sequences. CiE Daniel Goc, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
2015	A	`conf`	A Physically Universal Cellular Automaton. ITCS Luke Schaeffer
2015	—	`conf`	A Physically Universal Quantum Cellular Automaton. Automata Luke Schaeffer
2015	J	`jnl`	Closed, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences. CoRR Luke Schaeffer, Jeffrey O. Shallit
2015	B	`conf`	Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. ISAAC Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015	J	`jnl`	Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games. Electron. Colloquium Comput. Complex. Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
2015	J	`jnl`	The Classification of Reversible Bit Operations. CoRR Scott Aaronson, Daniel Grier, Luke Schaeffer
2015	J	`jnl`	The Classification of Reversible Bit Operations. Electron. Colloquium Comput. Complex. Scott Aaronson, Daniel Grier, Luke Schaeffer
2014	J	`jnl`	A Physically Universal Cellular Automaton. Electron. Colloquium Comput. Complex. Luke Schaeffer
2014	J	`jnl`	Avoiding Three Consecutive Blocks of the Same Size and Same Sum. J. ACM Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey O. Shallit
2014	J	`jnl`	Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance. CoRR Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, Jeffrey O. Shallit
2013	C	`conf`	Ostrowski Numeration and the Local Period of Sturmian Words. LATA Luke Schaeffer
2013	C	`conf`	Subword Complexity and k-Synchronization. Developments in Language Theory Daniel Goc, Luke Schaeffer, Jeffrey O. Shallit
2012	J	`jnl`	An Improved Lower Bound for Stack Sorting CoRR Luke Schaeffer
2012	J	`jnl`	Ostrowski Numeration and the Local Period of Sturmian Words CoRR Luke Schaeffer
2012	J	`jnl`	The Critical Exponent is Computable for Automatic Sequences. Int. J. Found. Comput. Sci. Luke Schaeffer, Jeffrey O. Shallit
2012	J	`jnl`	The Subword Complexity of k-Automatic Sequences is k-Synchronized CoRR Daniel Goc, Luke Schaeffer, Jeffrey O. Shallit
2011	J	`jnl`	Avoiding Three Consecutive Blocks of the Same Size and Same Sum CoRR Julien Cassaigne, James D. Currie, Luke Schaeffer, Jeffrey O. Shallit
2011	J	`jnl`	Decidability and Shortest Strings in Formal Languages CoRR Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit
2011	—	`conf`	Decidability and Shortest Strings in Formal Languages. DCFS Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit