We first provide a framework to formalise infinite sequences of qubits as states of a suitable C*-algebra. Thereafter we introduce an analog of Martin-Löf's notion. We show that for classical bit sequences the two notions coincide. We also discuss quantum Kolmogorov complexity for finite sequences of qubits and its relationship to quantum Martin-Löf randomness. Finally we consider an effective version of the Shannon-McMillan-Breiman theorem in the quantum setting.
This is joint work with Volkher Scholz. Paper available at https://arxiv.org/abs/1709.08422.
In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on punctual equivalence relations, i.e., primitive recursive equivalence relations with domain ω. We show that Peq has much structure, being a dense distributive lattice. This contrasts with all other known degree structures on equivalence relations. Finally, we use our analysis to investigate the online content of computably categorical equivalence structures and prove many elementary differences.
This is joint work with Nikolay Bazhenov, Keng Meng Ng, and Andrea Sorbi.
Joint work with Barbara Csima and Keng Meng Ng.
The isomorphism problem for a family of group actions asks whether two given elements of the universe belong to the same orbit under the action. Many isomorphism problems have NP-intermediate status. Another class of problems with NP-intermediate status are certain compressibility questions for Boolean functions, including the Minimum Circuit Size Problem (MCSP): Given a function table and an integer k, does there exist a circuit of size at most k that computes the function?
We develop an approach to establish reductions from isomorphism problems to compressibility problems that is inspired by the constant-round interactive proof system for the complement of Graph Isomorphism. The approach yields randomized polynomial-time reductions with zero-sided error from a broad class of isomorphism problems to the problem of compressibility by short efficient programs (known as MKTP).
This talk is based on joint work with Eric Allender, Joshua Grochow, Cris Moore, and Andrew Morgan; see here for the paper.
In this work, we consider the open and clopen Ramsey theorems (also known as Nash-Williams theorem). It is known that both the open and the clopen Ramsey theorem are equivalent to ATR0 over RCA0. However, if we move into the Weihrauch context, we will see that are several ways to phrase these principles as multivalued functions, and they exhibit very different behaviors. This is joint work with Alberto Marcone.
The majority of the talk will explain what flatness is, how it should be thought of, and how closely it relates to hypergraphs and Hrushovski's construction method. Model theory makes an appearance only in the second part, where I will share results pertaining to the specific family of geometries arising from Hrushovski's methods.
Consider two angles 0 < φ < ψ < π/2. Clearly 0 < tan(φ) < tan(ψ) < ∞. Is it possible that tan(ψ) = 2 tan(φ) and yet φ and ψ are both rational multiples of π? We show, using the method of Leopoldt's character coordinates, that this is impossible. This is used to prove a complexity classification of spin systems on any k-regular graphs with arbitrary real-valued edge functions.
I will also describe the edge-coloring problem, which is to assign k colors to the edges of a graph so that no two incident edges receive the same color. We show a complexity classification for the counting problem. Here the classification depends on an effective version of Siegel's theorem on finiteness of integer solutions for a specific algebraic curve.
All talks after spring break were virtual.
When a structure A is coded in a structure B, effective decoding i represented by a Medvedev reduction of A to B. Harrison-Trainor, Melnikov, Miller, and Montalbán  defined a notion of effective interpretation of A in B and proved that this is equivalent with the existence of computable functor, i.e., a pair of Turing operators, one taking copies of A to copies of B, and the other taking isomorphisms between copies of B to isomorphisms between the corresponding copies of A.
The class of undirected graphs and the class of linear orderings both lie on top under Turing computable embeddings. The standard Turing computable embeddings of directed graphs (or structures for an arbitrary computable relational language) in undirected graphs come with uniform effective interpretations. We give examples of graphs that are not Medvedev reducible to any linear ordering, or to the jump of any linear ordering. Any graph can be interpreted in a linear order using computable Σ03-formulas. Friedman and Stanley  gave a Turing computable embedding L of directed graphs in linear orderings. We show that there do not exist Lω1,ω-formulas that uniformly interpret the input graph G in the output linear ordering L(G). This is joint work with J. Knight, and S. Vatev . We have also a positive result — we prove that the class of fields are effectively interpreted in the class of Heisenberg groups. We discuss some questions around this and SL2(C). The second part is joint work with R. Alvir, W. Calvert, V. Harizanov, J. Knight, R. Miller, A. Morozov, and R. Weisshaar .
 H. Friedman and L. Stanley, “A Borel reducibility theory for classes of countable structures,” JSL, vol. 54(1989), pp. 894-914.
 M. Harrison-Trainor, A. Melnikov, R. Miller, and A. Montalbán, “Computable functors and effective interpretability,” JSL, vol. 82(2017), pp. 77-97.
 J. Knight, A. Soskova, S. Vatev “Coding in graphs and linear orderings”, to appear in JSL.
 R. Alvir, W. Calvert, V. Harizanov, J. Knight, R. Miller, A. Morozov, A. Soskova, and R. Weisshaar, “Interpreting a field in its Heisenberg group”, preprint, 2019.
In the first part, we will work with the effective analogues of the localization and prediction numbers, defined by Rosłanowski-Newelski and Blass, respectively. We use the effectivization method proposed by Rupprecht in order to work with new computability-theoretic notions in the effective Cichoń Diagram.
In the second part, we explore the different ways in which a set closed under Turing equivalence sits inside the real line. We will look at an application of a pathological order (achieved by a set closed under Turing equivalence) to the automorphism problem of the Turing degrees.