[Colloquium] [CS] 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: JCL 298

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 --------------
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/20220428/55eda120/attachment-0017.pdf>
-------------- next part --------------
_______________________________________________
One-Click Unsubscribe: https://mailman.cs.uchicago.edu/mailman/options/cs/vilterp%40cs.uchicago.edu?password=pekoapfe&unsub=1&unsubconfirm=1


When unsubscribing manually please use your cnetid at cs.uchicago.edu address to unsubscribe if your cnetid at uchicago.edu does not work.

cs mailing list  -  cs at mailman.cs.uchicago.edu
Edit Options and/or Unsubscribe: https://mailman.cs.uchicago.edu/mailman/listinfo/cs
More information here: https://howto.cs.uchicago.edu/techstaff:mailinglist