Midwest Computability Seminar

Midwest Computability Seminar

XXIX


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


VIDEOS:     San Mauro    Stull    Valenti    (Panopto)      San Mauro    Stull    Valenti   (YouTube)

SLIDES:     San Mauro    Stull    Valenti


The University of Chicago recommends that individuals wear a mask in indoor settings when others are present.

(See https://goforward.uchicago.edu/.)


DATE: Tuesday, November 1st, 2022

PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.

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



Speakers:

Schedule:


Abstracts:

Donald Stull

Title: Pinned distance sets using effective dimension

Abstract: Given a set E in the plane and a point x, the pinned distance set of E with respect to x is the set of distances between x and the points in E. Determining the Hausdorff dimension of pinned distance sets is a central open problem in geometric measure theory. In this talk, I will discuss how we can use effective methods to improve the bounds on the dimension of pinned distance sets.


Luca San Mauro

Title: Effectivizing the theory of Borel equivalence relations

Abstract: The study of the complexity of equivalence relations has been a major thread of research in diverse areas of logic. In descriptive set theory, one investigates Borel reductions of equivalence relations on Polish spaces. In computability theory, one focuses on computable reductions of countable equivalence relations. Despite the clear analogy between the two notions, for a long time the study of Borel and computable reducibility were conducted independently. Yet, a theory of computable reductions which blends ideas from both computability theory and descriptive set theory is rapidly emerging. In this talk, we will discuss differences and similarities between the Borel and the computable settings as we provide computable, or computably enumerable, analogs of fundamental concepts from the Borel theory. In particular, we concentrate on natural effectivizations of two classic concepts: orbit equivalence relations and the Friedman-Stanley jump. This is joint work with Uri Andrews.


Manlio Valenti

Title: The first-order part of computational problems

Abstract: Given a partial order (P,≤), a natural strategy to prove that a ≰ b is to present an example of some c ≤ a such that c ≰ b. In general, finding such a c can be very challenging.

In this talk, we will present a degree-theoretic operator on computational problems called "first-order part". This operator was introduced by Dzhafarov, Solomon, Yokoyama, and maps a multi-valued function f to the "strongest computational problem that is Weihrauch-below f". Characterizing the first-order part of a given problem can be challenging as well, but it proved to be a very useful tool, especially when comparing principles that are (relatively) high in the Weihrauch hierarchy. After a few examples, we will discuss some results on the algebraic properties of the first-order part, showing how they can simplify the characterization of the first-order part in many practical situations.


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.