A draft of my review for the Notices of the AMS (2019).
Moderator @ Theoretical Computer Science
In 2018 I was elected Moderator of the Stack Exchange Q&A site for Theoretical Computer Science,
cstheory.stackexchange.com
This site is to the theory groups in CS departments as MathOverflow is to math departments.
Computability theory is welcome… visit the site today.
Automatic Complexity 2014-2019
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.
| Student/consultant | Conference | Journal |
|---|---|---|
| Hyde (MA, 2013) | COCOON 2014 | Elec. J. Combinatorics (2015) |
| COCOA 2014 | Theoretical Computer Science (2015) | |
| Alikhani (MA, 2014); Pakravan, Saadat (MSc Fin.Eng., 2013) | Algorithmic Finance (2015) | |
| (written at CCR 2015) | Theory of Computing Systems (2017) | |
| (Castiglione 2015) | WoLLIC 2017 | Discrete Mathematics (2018) |
| (Kobayashi 2016) | (VAI 2015) | Experimental Mathematics (2019) |
| (Huggins 2016) | UCNC 2017 | |
| Liu (MA, 2017) | (ALH 2018) | |
| Yogi (MA, 2018) |
For instance, I gave a talk in the Seattle Probability Seminar organized by Soumik Pal and Chris Burdzy at the University of Washington Department of Mathematics.
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.
The paper is loosely coupled with the following software:
- Complexity Guessing Game
- Complexity Option Game
- Structure Function Calculator
These are gathered in some slides.com slides.
Shift registers fool finite automata @ WoLLIC and in Discrete Mathematics
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.
No modular iterative way to get joint distribution from covariance matrix
Suppose $A$, and $B$ are events with
$$\Pr(A)=3/12,\quad \Pr(B)=4/12,\quad\Pr(A\cap B)=0$$
Suppose $A’$ and $B’$ are events with
$$\Pr(A’)=3/12,\quad\Pr(B’)=8/12,\quad\Pr(A’\cap B’)=1/12$$
Notice that the covariance matrix $M$ for the Bernoulli random variables $1_A$, $1_B$ is the same as the one for $1_{A’}$, $1_{B’}$.
Now suppose we wanted to take any given joint distribution giving covariance matrix $M$ and extend it to the covariance matrix for $A$, $B$, $C$, where $\Pr(C)=\Pr(C\setminus(A\cup B))=5/12$.
We claim this is impossible if we are given the joint distribution of $A’$ and $B’$. That is, we claim there is no choice of probabilities concerning $C’$ that will give the right covariance matrix.
Note that $\Pr(C’)\in\{5/12, 7/12\}$ is necessary since $\mathrm{Var}(1_C)=\mathrm{Var}(1_{C’})$ is necessary. Moreover
$$0-(3/12)(5/12)=\mathrm{Cov}(A,C)=\mathrm{Cov}(A’,C’)=E(1_{A’}1_{C’})-E(1_{A’})E(1_{C’})=\Pr(A’\cap C’)-(3/12)(5/12\text{ or }7/12)$$
so
$$\Pr(A’\cap C’)=(3/12)(0\text{ or }2/12)=0\text{ or }6/144$$
Similarly for $B’$,
$$0-(4/12)(5/12)=\mathrm{Cov}(B,C)=\mathrm{Cov}(B’,C’)=E(1_{B’}1_{C’})-E(1_{B’})E(1_{C’})=\Pr(B’\cap C’)-(8/12)(5/12\text{ or }7/12)$$
so
$$\Pr(B’\cap C’)=-20/144+(40\text{ or }56)/144= (20\text{ or }36)/144$$
The choice $\Pr(C’)=5/12$. $\Pr(A’\cap C’)=0$, $\Pr(B’\cap C’)=20/144$ gives $\Pr(A’\cup B’\cup C’)=156/144>1$, contradiction.
The other choice $\Pr(C’)=7/12$, $\Pr(A’\cap C’)=6/144$, $\Pr(B’\cap C’)=36/144$ gives $\Pr(C’\setminus(A’\cup B’))\ge 84/144-6/144-36/144=42/144=7/24$, so $\Pr(A’\cup B’\cup C’)\ge 10/12 + 7/24 > 1$, also contradiction.
Q.E.D.
Statistics of rental prices
Spring 2017 saw the last MATH 373 class ever, as we transitioned to MATH 372 combining MATH 371 (probability) and 373 (statistics).
Final cohort MATH 373 students Tiffany Eulalio and Jake Koki’s term paper on apartment rental prices in Honolulu has been accepted for publication in undergraduate journal Manoa Horizons volume II.
On the complexity of automatic complexity
The paper “On the complexity of automatic complexity” is to appear in Theory of Computing Systems, in a post-conference journal issue for Computability, Complexity and Randomness 2015 held in Heidelberg, Germany.
While it is not known whether the set of strings of maximal nondeterministic automatic complexity is NP-complete (hence the paper is called “On the complexity…” rather than just “The complexity…”), the paper shows that the more general problem for automatic complexity of equivalence relations is NP-complete. It is also shown that the set of highly complex strings is not context-free.
Superposition as memory @ UCNC17
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$.
Details in the paper: Superposition as memory: unlocking quantum automatic complexity which appeared in the Lecture Notes in Computer Science volume of the conference Unconventional Computation and Natural Computation (UCNC) 2017.