• 8/27/2019 4PM in room B231, André Nies, University of Auckland, New Zealand
  Title: Random sequences of quantum bits
  Martin-Löf (1966) formalised the intuitive notion of randomness for infinite sequences of bits via algorithmic tests. What if we replace classical bits by quantum bits?

  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.

  
  Dinner: Vientiane Palace (151 W. Gorham St.) at 6PM at 6PM


• 9/3/2019 4PM, Luca San Mauro, Vienna University of Technology, Austria
  Title: The complexity of punctual equivalence relations
  The complexity of equivalence relations received much attention in the literature. In general, a reduction of an equivalence relation R on X to an equivalence relation S on Y is a function f: X → Y that injectively maps R-classes to S-classes. In descriptive set theory, one assumes that X and Y are Polish spaces and f is Borel. In computability theory, one assumes that X=Y=ω and f is computable. To compare the complexity of equivalence relations which are computable, researchers also considered feasible variants of computable reducibility, such as the polynomial-time reducibility.

  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.

  
  Dinner: Great Dane Pub (123 E. Doty St.) at 6PM


• 9/10/2019 4PM, Rod Downey, Victoria University of Wellington, New Zealand
  Title: Realizing c.e. degrees in Π⁰₁-classes
  The Kreisel Basis Theorem says that each Π⁰₁-class has a member of c.e. Turing degree. What collections of c.e. degrees can be realized as exactly the c.e. members of some Π⁰₁-class? For example, using a Π⁰₁-class of Martin-Löf random sets, we see that we can realize the collection of Turing complete c.e. sets, and old work of Jockusch and Soare shows that {e | W_e incomplete and noncomputable} cannot be realized in a single Π⁰₁-class. Clearly, realizable collections will be index sets. We give a complete (and perhaps surprising) answer to this question, and also introduce a new notion of a representation of an index set.

  Joint work with Barbara Csima and Keng Meng Ng.

  
  Dinner: Ichiban Sichuan Restaurant (610 S. Park St.) at 6PM


• 9/17/2019 4PM, Iskander Kalimullin, Kazan Federal University, Russia
  Title: Punctual structures and punctual computability on a cone
  We will study punctual (primitive recursive) algorithms on the structures. In particular, I will give a model-theortic description for intristically primitive recursive sets for algebraic structures. Also, we will study the relative categoricity on a cone and its effective and non-effective characterizations. The results obtained jointly with A. Melnikov and A. Montalbán.


• 9/24/2019 4PM, Jun Le Goh, UW
  Title: Inseparable Π¹₁-sets
  We investigate analogs of the theory of effectively inseparable pairs of recursively enumerable sets to Π¹₁-sets of numbers and Π¹₁-sets of reals. These are used to derive completeness results, such as an unpublished result of Harrington about jump hierarchies.


• 10/1/2019 4PM, Dieter van Melkebeek, UW computer science department
  Title: Isomorphism problems and minimum circuit size
  Whereas NP-complete problems are polynomial-time reducible to each other by definition, little is known about reductions between well-known candidate NP-intermediate problems. In this talk, we present reductions between two types of such problems: isomorphism problems and compressibility problems.

  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.



• 10/8/2019 4PM, Manlio Valenti, visiting UW from University of Udine, Italy
  Title: The open and clopen Ramsey theorem in the Weihrauch lattice
  While the lower levels of the Weihrauch lattice have been extensively studied, the higher levels remain mostly unexplored. Recently, in a Dagstuhl meeting, Marcone raised the question about what the Weihrauch hierarchy looks like if we consider principles that are at the level of ATR₀ or Π¹₁-CA₀. This started the quest for an "ATR₀-analogue" in the Weihrauch lattice.

  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 ATR₀ over RCA₀. 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.



• 10/11/2019 4PM (department colloquium in room B239), Omer Mermelstein, UW
  Title: Generic flat pregeometries
  In model theory, the tamest of structures are the strongly minimal ones - those in which every equation in a single variable has either finitely many or cofinitely many solutions. Algebraically closed fields and vector spaces are the canonical examples. Zilber’s conjecture, later refuted by Hrushovski, states that the source of geometric complexity in a strongly minimal structure must be algebraic. The property of "flatness" (strict gammoid) of a geometry (matroid) is that which guarantees Hrushovski's construction is devoid of any associative structure.

  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.



• 10/15/2019 4PM, Wim Ruitenburg, Marquette University, Milwaukee, Wisconsin
  Title: The unsettled story of the proof interpretation
  Intuitionistic logic is broadly accepted as the constructive logic. Its justification through a proof interpretation is not. We present aspects of the arguments for one or the other version of a proof interpretation for constructive logic.


• 10/22/2019 4PM, Dima Sinapova, University of Illinois at Chicago
  Title: Singularizing cardinals
  It is an old theorem that if a regular cardinal κ is singularized to countable cofinality, while preserving cardinals, then ◻κω holds in the outer model. Many strengthenings of this theorem have been obtained as well. We prove that this does not generalize to uncountable cofinalities. We show that after the right kind of preparation, in the Magidor model of singularizing κ to uncountable cofinality (and so while preserving cardinals), all intermediate forms of square at κ fail. This is another instance of the familiar phenomenon that singular cardinals of countable cofinality can behave quite differently than those of uncountable cofinality. This is joint work with Maxwell Levine.
  
  Dinner: Canteen (111 S. Hamilton St.) at 6PM


• 10/29/2019 4PM, Filippo Calderoni, University of Illinois at Chicago
  Title: The bi-embeddability relation for countable abelian groups
  In this talk we shall discuss the Borel complexity of the bi-embeddability relation for countable torsion abelian groups. First, we shall show that bi-embeddability is not a Borel equivalence relation in the case of p-groups, for a fixed prime p. Next, we will show that the isomorphism and bi-embeddability relations for countable torsion abelian groups are incomparable up to Borel reducibility. To contrast this result, we shall discuss how bi-embeddability is strictly simpler than isomorphism under Δ¹₂-reducibility with some very mild large cardinal assumptions. This is joint work with Simon Thomas.
  
  Dinner: Great Dane Pub (123 E. Doty St.) at 6PM


• 11/5/2019 4PM, Uri Andrews, UW
  Postponed to Feb. 11, 2020


• 11/12/2019 4PM, James Hanson, UW
  Title: Skolemization in continuous logic (specialty exam)
  Skolemization is a relatively trivial operation in discrete logic, but in the context of continuous logic, it becomes surprisingly subtle. Naive Skolemization isn't always possible without destroying the metric, even in 'finite' (i.e., compact) structures. We introduce a notion of 'weak Skolemization, which is classically equivalent to ordinary Skolemization, and show that any weakly Skolemizable theory is weakly Skolemizable without increasing the cardinality of the language. Finally, we discuss progress towards characterizing weakly Skolemizable theories.


• 11/19/2019 4PM, Jin-Yi Cai, UW computer science department
  Title: Offerings from the classification program for counting problems
  I will give a sample of results in the complexity classification program for counting problems. I would like to illustrate this research by some concrete results of a different mathematical flavor.

  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.

• 1/21/2020 4PM (department colloquium/special lecture in room B139), Peter Cholak, University of Notre Dame, Indiana
  Title: What can we compute from solutions to combinatorial problems?
  This will be an introductory talk to an exciting current research area in mathematical logic. Mostly we are interested in solutions to Ramsey's Theorem. Ramsey's Theorem says for colorings C of pairs of natural numbers, there is an infinite set H such that all pairs from H have the same constant color. H is called a homogeneous set for C. What can we compute from H? If you are not sure, come to the talk and find out!
  
  Dinner: Canteen (111 S. Hamilton St.) at 6PM


• 1/22/2020 4PM, Peter Cholak, University of Notre Dame, Indiana
  Title: SRT²₂ does not imply RT²₂ in ω-models, part 1
  In this and the next talk, our goal is to work though the 2nd and 3rd sections of Monin and Patey’s paper "SRT²₂ does not imply RT²₂ in ω-models”.


• 1/27/2020 4PM (in room B215), Peter Cholak, University of Notre Dame, Indiana
  Title: SRT²₂ does not imply RT²₂ in ω-models, part 2
  Continuation of part 1.


• 1/28/2020 4PM, Andy Zucker, University of Lyon, France
  Title: A direct solution to the generic point problem
  Angel, Kechris, and Lyons asked the following question: Given a Polish group G with metrizable universal minimal flow (UMF), must the UMF have a comeager orbit? This question was answered affirmatively, first by myself for the case that G is the automorphism group of a countable structure, and then by Ben Yaacov, Melleray, and Tsankov in full generality. A peculiar consequence of this theorem is the following observation: If G is a Polish group and X is any minimal G-flow with only meager orbits, then the UMF of G must be non-metrizable. In this talk, I will give a new, direct proof of this theorem by showing that if X is a minimal G-flow with all orbits meager, then one can construct a new, more complicated flow using X which is non-metrizable.
  
  Dinner: Great Dane Pub (123 E. Doty St.) at 6PM


• 1/29/2020 4PM (department colloquium in room B239), Andy Zucker, University of Lyon, France
  Title: Topological dynamics of countable groups and structures
  We give an introduction to the abstract topological dynamics of topological groups, i.e., the study of the continuous actions of a topological group on a compact space. We are particularly interested in the minimal actions, those for which every orbit is dense. The study of minimal actions is aided by a classical theorem of Ellis, who proved that for any topological group G, there exists a universal minimal flow (UMF), a minimal G-action which factors onto every other minimal G-action. Here, we will focus on two classes of groups: a countable discrete group and the automorphism group of a countable first-order structure. In the case of a countable discrete group, Baire category methods can be used to show that the collection of minimal flows is quite rich and that the UMF is rather complicated. For an automorphism group G of a countable structure, combinatorial methods can be used to show that sometimes, the UMF is trivial, or equivalently that every continuous action of G on a compact space admits a global fixed point.
  
  Dinner: Mr. Kimchi Modern Korean (225 King St.) at 6:30PM


• 2/3/2020 4PM (in room B215), Peter Cholak, University of Notre Dame, Indiana
  Title: SRT²₂ does not imply RT²₂ in ω-models, part 3
  Continuation of part 2.


• 2/4/2020 4PM, Alexandra Soskova, University of Sofia, Bulgaria
  Title: Coding and decoding in classes of structures
  Friedman and Stanley [1] introduced Borel embeddings as a way of comparing classification problems for different classes of structures. A Borel embedding of a class K in a class K' represents a uniform procedure for coding structures from K in structures from K'. Many Borel embeddings are actually Turing computable.

  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 [2] 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 Σ⁰₃-formulas. Friedman and Stanley [1] 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 [3]. 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 [4].

  References:

  [1] H. Friedman and L. Stanley, “A Borel reducibility theory for classes of countable structures,” JSL, vol. 54(1989), pp. 894-914.

  [2] M. Harrison-Trainor, A. Melnikov, R. Miller, and A. Montalbán, “Computable functors and effective interpretability,” JSL, vol. 82(2017), pp. 77-97.

  [3] J. Knight, A. Soskova, S. Vatev “Coding in graphs and linear orderings”, to appear in JSL.

  [4] 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.

  
  Dinner: The Globe Restaurant (309 N. Henry St.) at 6PM


• 2/11/2020 Midwest Model Computability Seminar, University of Chicago
  Brown bag lunch: in Ryerson 352 at 1PM
  Speakers:
  • 2PM, Jun Le Goh, UW
    Title: Computing descending sequences in linear orderings
    We investigate how hard it is to compute a descending sequence in a given ill-founded linear ordering, in the framework of Weihrauch reducibility. Joint work with Arno Pauly and Manlio Valenti.
    
    
  • 2:50PM, Rachael Alvir, University of Notre Dame, Indiana
    Title: Scott sentences
    In this talk, we will give various results on Scott sentences.
    
    
  • 4PM, Tejas Bhojraj, UW
    Title: Quantum algorithmic randomness
    I will introduce the basic notions of quantum algorithmic randomness and then state a few results. Time permitting, I will sketch proofs of the following two results: (1) quantum Martin-Löf randomness is equivalent to quantum Solovay randomness and (2) quantum Schnorr random states satisfy a quantum version of the Law of large numbers.
    
    
  • 4:50PM, Neil Lutz, Iowa State University, Ames
    Title: Fractal slices, projections, and products via algorithmic dimension
    This talk will describe recent progress in using Kolmogorov complexity and point-to-set principles to remove structural hypotheses from prominent classical theorems in fractal geometry. These include Marstrand's slicing theorem, Marstrand's projection theorem, and a characterization of packing dimension in terms of product sets.
    
    
  Dinner: Jolly Pumpkin (5215 S. Harper Ave.) at 5:50PM


• 2/12/2020 4PM (in room B215), William Chan, University of North Texas, Denton
  Title: The ultrapowers of the partition measures on the first uncountable cardinal
  Solovay showed that the axiom of determinacy implies the club filter on the first uncountable cardinal is a measure. Martin generalized this argument to show the axiom of determinacy implies the first uncountable cardinal has the strong partition property. The partition properties can then be used to define partition measures on the function space. In this talk, we will give an overview of Martin's argument of using good codings of functions into the first uncountable cardinal and the boundedess principle to establish the partition relations. One will also discuss the almost everywhere continuity property of countable ordinal value functions and its role in producing lower bounds on the ultrapower of the first uncountable cardinal by the strong partition measure.
  
  Thursday, Feb. 13 (309 N. Henry St.) at 12noon
  Dinner: Fresco Thursday, Feb. 13 (227 State St.) at 6PM


• 2/14/2020 4PM (department colloquium in room B239), William Chan, University of North Texas, Denton
  Title: Definable infinitary combinatorics under determinacy
  The axiom of determinacy, AD, states that in any infinite two player integer game of a certain form, one of the two players must have a winning strategy. It is incompatible with the ZFC set theory axioms with choice; however, it is a succinct extension of ZF which implies many subsets of the real line possess familiar regularity properties and eliminates many pathological sets. For instance, AD implies all sets of reals are Lebesgue measurable and every function from the reals to the reals is continuous on a comeager set. Determinacy also implies that the first uncountable cardinal has the strong partition property which can be used to define the partition measures. This talk will give an overview of the axiom of determinacy and will discuss recent results on the infinitary combinatorics surrounding the first uncountable cardinal and its partition measures. I will discuss the almost everywhere continuity phenomenon for functions outputting countable ordinals and the almost-everywhere uniformization results for closed and unbounded subsets of the first uncountable cardinal. These will be used to describe the rich structure of the cardinals below the powerset of the first and second uncountable cardinals under determinacy assumptions and to investigate the ultrapowers by these partition measures.


• 2/18/2020 4PM, Uri Andrews, UW
  Title: Richness of implication in almost any logic
  Think up your favorite non-standard logic. I'll talk about how to show that it gives rise to a rich pre-order under implication. We'll show that any r.e. preorder can be computably embedded into the pre-order of your logic under implication. The reason that I don't need to know which is your favorite non-standard logic is that this relies on a theorem purely of recursion theory. Formally, I'll show that any r.e. pre-lattice (i.e. a structure (L, ∨, ∧, 0, 1, ≤), where $∨, ∧$ are computable and ≤ is r.e.) in which the classes of 0 and 1 are effectively inseparable must computably embed any r.e. preorder (i.e., a preorder (L, ≤) where ≤ is r.e.). I'll hopefully talk about some applications to non-standard logics. (This is joint work with Andrea Sorbi.)


• 3/3/2020 4PM, Josiah Jacobsen-Grocott, UW
  Title: Types of minimal pairs in the enumeration degrees
  We prove that the enumeration degrees have strong minimal pairs while they do not have a stronger type of minimal pair we call a strong superminimal pair. We leave open the question of a superminimal pair in the enumeration degrees.


• 3/10/2020 4PM, Linda Brown Westrick, Pennsylvania State University, University Park
  Title: Universality in multi-dimensional shifts of finite type
  We construct Z²-shifts of finite type (SFTs) at every computable level of the hierarchy of topological completely positive entropy (TCPE), answering Barbieri and García-Ramos, who asked if there was one at level 3. Furthermore, we show that the property of TCPE in Z²-SFTs is coanalytic complete. Thus there is no simpler description of TCPE in Z²-SFTs than in the general case.
  
  Dinner: Taste of Sichuan (515 State St.) at 6PM


• 3/24/2020 4PM (virtual talk), Mariya Soskova, UW
  Title: The enumeration degrees: the known and the unknown
  Enumeration reducibility captures a natural relationship between sets of natural numbers in which positive information about the first set is used to produce positive information about the second set. By identifying sets that are reducible to each other, we obtain an algebraic representation of this reducibility as a degree structure. The structure of the enumeration degrees has been the focus of active research in recent years. Motivation for the interest in this area comes from its nontrivial connections to the study of the Turing degrees, specifically with respect to longstanding open problems, such as the rigidity problem, and to problems from effective mathematics, where Turing reducibility is sometimes not sufficient to measure the effective content of an object. I will give an overview of this research. I will discuss different aspects of the degree structure: definability, automorphisms, decidability and connections to other fields of mathematics. For each topic, I will try to outline the boundary of what we know and list open problems that mark the next step on our path to understanding this structure.


• 4/21/2020 4PM (virtual talk), James Hanson, UW
  Title: Definability and categoricity in continuous logic (thesis defense)
  Definable sets in continuous logic are known to be poorly behaved in certain continuous theories. After examining some examples of this behavior, we will define and characterize a natural condition ensuring the prevalence and malleability of definable sets. As an application of this machinery, we will then develop the concept of strongly minimal sets in continuous logic in an effort to find conditions under which the classical Baldwin-Lachlan characterization of uncountably categorical theories generalizes to the context of inseparably categorical continuous theories.


• 4/28/2020 4PM (virtual talk), Iván Ongay Valverde, UW
  Title: Relations between set theory and computability theory: The case for localization numbers and sets closed under Turing equivalence (thesis defense)
  This talk will be divided in two distinct parts. In both of them, we will use different techniques of set theory in the setting of computability theory.

  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.