[CS] REMINDER: Tiago Royer Candidacy Exam/Apr 10, 2025
via cs
cs at mailman.cs.uchicago.edu
Mon Apr 7 10:18:24 CDT 2025
This is an announcement of Tiago Royer's Candidacy Exam.
===============================================
Candidate: Tiago Royer
Date: Thursday, April 10, 2025
Time: 10 am CST
Location: JCL 298
Title: The Kolmogorov Complexity of Attractive Degrees
Abstract: In the context of asymptotic notions of computability, it is possible to define a metric, called the Hausdorff distance H(a, b) between the degrees a and b. This metric has the remarkable property of being 0,1/2,1-valued, and as a consequence, for every degree a there is either measure-1 many degrees b at a distance 1/2 from a, or measure-1 many degrees at a distance 1 from a. The former are called attractive degrees, and the latter dispersive.
We prove the following sufficient condition for a set A to have attractive degree: if K(A \upharpoonright n) > 2K(n) for all n, then A has attractive degree. We explore the implications of this condition, including the connection with the open problem of finding a minimal degree with high Hausdorff dimension.
Advisors: Janos Simon
Committee: Stuart Kurtz, Denis Hirschfeldt, Janos Simon
More information about the cs
mailing list