Midwest Computability Seminar

Midwest Computability Seminar

XXXIII


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 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.

DATE: Tuesday, November 12th, 2024

PLACE: John Crerar Library Building 390, The University of Chicago.
5730 South Ellis Avenue, Chicago, IL 60637 (see maps.uchicago.edu).

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


Speakers:

Schedule:

Abstracts:


Jacob Fiedler

Title: Universal sets for projections

Abstract: Marstrand's projection theorem is one of the most prominent results in geometric measure theory. Essentially, it states that given any Borel set, its orthogonal projections in almost every direction have the maximum possible size. In this talk, we consider variants of Marstrand's projection theorem that hold for classes of sets instead of individual sets and sets of directions instead of individual directions. In particular, we discuss how assuming the sets in a class have a greater degree of "regularity", or similarity across scales, leads to improved bounds on the size of these sets of directions (which we call universal sets). We use Kolmogorov complexity and other tools from the study of algorithmic randomness throughout, connecting pointwise statements to this classical problem in geometric measure theory through the point-to-set principle of Lutz and Lutz. This talk is based on joint work with Don Stull.


Gabriela Laboska

Title: Some Computability-theoretic Aspects of Partition Regularity over Algebraic Structures

Abstract: An inhomogeneous system of linear equations over a ring R is partition regular if for any finite coloring of R, the system has a monochromatic solution. In 1933, Rado showed that an inhomogeneous system is partition regular over ℤ if and only if it has a constant solution. Following a similar approach, Byszewski and Krawczyk showed that the result holds over any integral domain. In 2020, Leader and Russell generalized this over any commutative ring R, with a more direct proof than what was previously used. We analyze some of these combinatorial results from a computability-theoretic point of view, starting with a theorem by Straus used directly or as a motivation to many of the previous results on the subject.


Ang Li

Title: Countable Ordered Groups and Weihrauch Reducibility

Abstract: It is known that a countable ordered group has order type ℤαℚε, where α is an ordinal and ε is either 0 or 1. This theorem falls into Π11-CA0, the highest of the big five axiom systems in reverse mathematics. In this talk, we study this theorem using Weihrauch reducibility. Given a countable ordered group, we shall study the uniform computational power of outputting some of α, ε, and the order-preserving function.


Mariya Soskova

Title: Enumeration Weihrauch reducibility

Abstract: Enumeration Weihrauch (eW) reducibility is a variant of Weihrauch reducibility that replaces Turing functionals by enumeration operators, using a notion of "positive information" computation. In this setting, several of the benchmark choice problems in the Weihrauch setting become separated. We discuss some of the more striking examples and their proofs. We then turn towards examining the structural properties of the eW degrees in search for a first-order difference with the  Weihrauch degrees. This is joint work with Alice Vidrine.


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.