Midwest Computability Seminar

Midwest Computability Seminar

XXXIV


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, the University of Wisconsin-Madison, and the University of Illinois Chicago. It meets once or twice per semester, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

DATE: Tuesday, April 1st, 2025

PLACE: SEO (Science and Engineering Offices) 636, The University of Illinois Chicago
851 South Morgan Street, Chicago IL
PLEASE NOTE THE NEW LOCATION
The suggested parking location is Parking Lot 5, East Campus at the corner of Morgan and Roosevelt (map).
There is also a parking structure at Halsted and Taylor.

REMOTE ATTENDANCE: https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09
Meeting ID: 997 5433 2165
Passcode: midwest


Speakers:

Schedule:


Abstracts:


Natasha Dobrinen

Title: Computability theoretic aspects of big Ramsey degrees

Abstract: In this talk, we will give an introduction to big Ramsey degrees of homogeneous structures.  Then we will concentrate on computability theoretic aspects and discuss work done in the area by various logicians, including work by Cholak, Dobrinen, McCoy.


Denis Hirschfeldt

Title: Attractive and Dispersive Degrees

Abstract: The upper density of the symmetric difference between two sets of natural numbers gives a notion of distance that can be used to define a metric on the Turing degrees. By work of Monin, this metric is (0,1/2,1)-valued. A degree a is attractive if almost every degree is at distance 1/2 from a, and dispersive otherwise. I will discuss joint work with Jockusch and Schupp, as well as more recent work of Royer, on the distribution of attractive and dispersive degrees, and their connections with the interplay between effective randomness and genericity.


Andrew Marks

Title: The recursive compression method for proving incomputability results

Abstract: We discuss a technique called recursive compression for proving incomputability results. The method has developed independently in mathematics and theoretical computer science, and gives a way of showing some set is incomputable by reducing the halting problem to it. Recursive compression was used by Durand, Romashchenko, and Chen in 2008 to give a new proof that the Wang tiling problem is incomputable. In quantum information theory, recursive compression was used by Ji, Natarajan, Vidick, Wright, and Yuen in 2020 to prove the MIP*=RE result that the halting problem is reducible to approximating the quantum value of a nonlocal game. Their result implies a negative answer to the longstanding Connes embedding problem in operator algebras.

We formulate a general recursive compression lemma which abstracts the technique used in these applications. A recursive compression f of a set A ⊂ 2ω is a polytime computable function which takes as input a program e computing a string x in exponential time, and outputs a program f(e) computing a string y in polynomial time so that x ∈ A iff y ∈ A. If A has a recursive compression, and A and its complement are nonempty, then A is incomputable. We also show a converse of the recursive compression lemma: the halting problem is polytime reducible to an r.e. set if and only if there is a recursive compression. Finally, we generalize the recursive compression lemma throughout the arithmetical hierarchy, giving a way to show that a language is Σ0n-hard using recursive compression. This is joint work with Seyed Sajjad Nezhadi and Henry Yuen.


Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.