Course title: “Recursive functions and complexity”
Textbook title: “A second course in formal languages and automata theory” by J. Shallit
Despite the intimidating titles this is just a graduate introduction to automata, computability, and complexity.
Possible additional topics: Automatic complexity and Python programming.
At the Association for Symbolic Logic Annual Meeting at CUNY Graduate Center in Manhattan, NY, I gave a talk in the Special Session on Computability Theory on joint work with Lu Liu.
Slides are available.
The Simons Foundation under the program Collaboration Grants for Mathematicians (#315188 to Bjørn Kjos-Hanssen, grant title “Automatic Complexity”) supported my travel during 2014–2019.
Year
Trips
2014 – 2015
COCOA 2014 (Maui); U. Washington; Varieties of Algorithmic Information; CCR, Heidelberg; Haidar to Arizona Winter School
2015 – 2016
ASL Annual Meeting, UConn (myself and Beros); SIAM Meeting on Discrete Math, Atlanta
2016 – 2017
WoLLIC, London; UCNC, Arkansas
2017 – 2018
Workshop on Computability Theory, Waterloo
2018 – 2019
Computability Theory and Foundations of Mathematics, Tokyo; Joint Math Meetings, Baltimore
Nine subprojects
Here are papers produced about automatic complexity, many with Master’s students.
Conferences in parentheses are those with no published proceedings.
Students or consultants in parentheses discussed the topic but were not coauthors.
Title:
Kolmogorov structure functions for automatic complexity
Abstract:
We study an analogue of Kolmogorov’s notion of structure function, introduced in 1973, with Kolmogorov complexity replaced by Shallit and Wang’s (2001) automatic complexity. We discuss the prospects for using it for model selection in statistics. We prove an upper bound which is piecewise smooth, related to the binary entropy function, and appears to be fairly sharp based on numerical evidence.
LFSRs (linear feedback shift registers) are popular pseudorandomness generators.
In a new project we show that they generate output (often called $m$-sequences) of maximal (nondeterministic path-based) automatic complexity. At this point we have an experimental result, one which would have probability $2^{-93}$ to occur “by chance”, as well as a theoretical but sub-optimal result.
Moreover, an $m$-sequence of length 31 provides an example of a word $x$ such that
$$
A^-(x)=A_N(x)+2
$$
where $A_N$ is nondeterministic path-based automatic complexity, and $A^-$ is non-total deterministic automatic complexity.
Such an example (where $A^-(x)-A_N(x)>1$) was not known before the consideration of LFSRs in this area. That consideration was an idea of Jason Castiglione.
The paper has been accepted at WoLLIC 2017 and in journal form for Discrete Mathematics (2018).
This project was presented at the poster session of the SIAM Conference on Discrete Mathematics 2016 in Atlanta, Georgia. The session was otherwise dominated by interesting work on RNA pseudoknots and chord diagrams (3 out of 6 posters) which in the case of the work of the Biocomplexity Institute researchers Ricky Chen and Thomas Li involves modeling with multiply context-free grammars.
Imagine a lock with two states, locked and unlocked, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states locked and unlocked, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.