Luke Schaeffer

CSL Conference 2022 Conference Paper

Decidability for Sturmian Words

• Philipp Hieronymi
• Dun Ma
• Reed Oei
• Luke Schaeffer
• Christian Schulz 0013
• Jeffrey O. Shallit

We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly ω-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.

TCS Journal 2021 Journal Article

Ostrowski-automatic sequences: Theory and applications

• Aseem Baranwal
• Luke Schaeffer
• Jeffrey Shallit

We extend the notion of k-automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al. , and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation.

STOC Conference 2020 Conference Paper

Interactive shallow Clifford circuits: quantum advantage against NC¹ and beyond

• Daniel Grier
• Luke Schaeffer

FOCS Conference 2019 Conference Paper

A Quantum Query Complexity Trichotomy for Regular Languages

• Scott Aaronson
• Daniel Grier
• Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity Θ(1), Θ̃(√ n), or Θ(n). The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we show can have query complexity Θ(n c ) for all computable c [1/2, 1]. Our result implies an equivalent trichotomy for the approximate degree of regular languages, and a dichotomy-either Θ(1) or Θ(n)-for sensitivity, block sensitivity, certificate complexity, deterministic query complexity, and randomized query complexity. The heart of the classification theorem is an explicit quantum algorithm which decides membership in any star-free language in Õ(√n) time. This well-studied family of the regular languages admits many interesting characterizations, for instance, as those languages expressible as sentences in first-order logic over the natural numbers with the less-than relation. Therefore, not only do the star-free languages capture functions such as OR, they can also express functions such as "there exist a pair of 2's such that everything between them is a 0. " Thus, we view the algorithm for star-free languages as a nontrivial generalization of Grover's algorithm which extends the quantum quadratic speedup to a much wider range of string-processing algorithms than was previously known. We show a variety of applications-new quantum algorithms for dynamic constant-depth Boolean formulas, balanced parentheses nested constantly many levels deep, binary addition, a restricted word break problem, and path-discovery in narrow grids-all obtained as immediate consequences of our classification theorem.

STOC Conference 2019 Conference Paper

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

• Adam Bene Watts
• Robin Kothari
• Luke Schaeffer
• Avishay Tal

Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.

TCS Journal 2017 Journal Article

Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability

• Chen Fei Du
• Hamoon Mousavi
• Eric Rowland
• Luke Schaeffer
• Jeffrey Shallit

We use a decision procedure for the “Fibonacci-automatic” words to solve problems about a number of different sequences. In particular, we prove that there exists an aperiodic infinite binary word avoiding the pattern x x x R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.