[Colloquium] Reminder - Tiago Royer MS Presentation/May 13, 2022

[Megan Woodward]

This is an announcement of Tiago Royer's MS Presentation
===============================================
Candidate: Tiago Royer

Date: Friday, May 13, 2022

Time:  3 pm CST

Location: Exam will now be held fully remote, please see zoom link below

Remote Location: https://uchicago.zoom.us/j/94748973840?pwd=VWhnck9ZTFBQbkplVDQ4bjJLMmdQQT09<https://www.google.com/url?q=https://urldefense.com/v3/__https://uchicago.zoom.us/j/94748973840?pwd%3DVWhnck9ZTFBQbkplVDQ4bjJLMmdQQT09__;!!BpyFHLRN4TMTrA!5KjXVIwKMY2K0KcjGUVRQdoEWoPj2vBx7kOWlEItRzVsatE-Rm27zJjzVFN5QmuMIg6siVTm59unB074oviHebvZIXA$&sa=D&source=calendar&ust=1652299493616970&usg=AOvVaw3zWfGq0kYgsUv1YAspZ4ul>

M.S. Paper Title: Asymptotic notions of computability: minimal pairs and randomness

Abstract: The concepts of dense computability, generic computability, coarse computability, and effective dense computability all generalize the notion of computability by requiring the algorithm to get the right answer only for "most of the inputs", rather than for all inputs (in a similar way that average-case complexity talks about expected running time, rather than imposing an upper bound in the running time of all inputs). These asymptotic notions of computability give rise to a degree structure analogous to the Turing degrees, but with different properties. In this paper we focus on minimal pairs and the level of randomness that they demand. We survey the main results in the area, and additionally settle the question of the number of minimal pairs for generic reducibility in the opposite direction that happens with the other reducibilities.

Advisors: Denis Hirschfeldt and Janos Simon (co-advisor)

Committee Members: Janos Simon, Denis Hirschfeldt, and Stuart Kurtz


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220513/769fb804/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: main.pdf
Type: application/pdf
Size: 487041 bytes
Desc: main.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220513/769fb804/attachment-0001.pdf>