- 1/21/2020 4PM,
Peter Cholak,
University of Notre Dame, Indiana

Title: TBATBA

Dinner: TBA at 6PM - 1/28/2020 4PM,
Andy Zucker,
University of Lyon, France

Title: TBATBA - 1/29/2020 4PM (department colloquium in room
**B239**), Andy Zucker, University of Lyon, France

Title: TBATBA - 2/4/2020 4PM,
Alexandra Soskova,
University of Sofia, Bulgaria

Title: Coding and decoding in classes of structuresTBA

Dinner: TBA at 6PM - 2/11/2020 4PM,
Uri Andrews,
UW

Title: Richness of implication in almost any logicThink 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/10/2020 4PM,
Linda Brown
Westrick, Pennsylvania State University, University Park

Title: TBATBA

Dinner: TBA at 6PM

- 8/27/2019 4PM in room B231,
André Nies,
University of Auckland, New Zealand

Title: Random sequences of quantum bitsMartin-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 relationsThe 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 Π^{0}_{1}-classesThe Kreisel Basis Theorem says that each Π^{0}_{1}-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 Π^{0}_{1}-class? For example, using a Π^{0}_{1}-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 Π^{0}_{1}-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 coneWe 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 Π^{1}_{1}-setsWe investigate analogs of the theory of effectively inseparable pairs of recursively enumerable sets to Π^{1}_{1}-sets of numbers and Π^{1}_{1}-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 sizeWhereas 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 latticeWhile 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_{0}or Π^{1}_{1}-CA_{0}. This started the quest for an "ATR_{0}-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

_{0}over RCA_{0}. 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 pregeometriesIn 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 interpretationIntuitionistic 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 cardinalsIt 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 groupsIn 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 Δ^{1}_{2}-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 problemsI 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.