Midwest Computability Seminar

Part iv

The Midwest Computability Seminar is meeting remotely in the fall of 2020. The recurring Zoom link is:


Meeting ID: 997 5433 2165

Passcode: midwest

YouTube video    Panopto video

This session will be held jointly with the Computability Theory and Applications Online Seminar.

DATE: Tuesday, September 29th, 2020

TIME: 3:00 - 4:00 PM CDT

SPEAKER: Christopher Porter - Drake University

Effective Dimension and the Intersection of Random Closed Sets

The connection between the effective dimension of sequences and membership in algorithmically random closed subsets of Cantor space was first identified by Diamondstone and Kjos-Hanssen. In this talk, I highlight joint work with Adam Case in which we extend Diamondstone and Kjos-Hanssen's result by identifying a relationship between the effective dimension of a sequence and what we refer to as the degree of intersectability of certain families of random closed sets (also drawing on work by Cenzer and Weber on the intersections of random closed sets). As we show, (1) the number of relatively random closed sets that can have a non-empty intersection varies depending on the choice of underlying probability measure on the space of closed subsets of Cantor space---this number being the degree of intersectability of a given family of random closed sets---and (2) the effective dimension of a sequence X is inversely proportional to the minimum degree of intersectability of a family of random closed sets, at least one of which contains X as a member. Put more simply, a sequence of lower dimension can only be in random closed sets with more branching, which are thus more intersectable, whereas higher dimension sequences can be in random closed sets with less branching, which are thus less intersectable, and the relationship between these two quantities (that is, effective dimension and degree of intersectability) can be given explicitly.

Past and Future Sessions

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.