BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Chris Porter (Drake University) DTSTART:20200514T180000Z DTEND:20200514T190000Z DTSTAMP:20260404T143402Z UID:OLS/4 DESCRIPTION:Title: Randomness extraction from a computability-theoretic perspective\nb y Chris Porter (Drake University) as part of Online logic seminar\n\n\nAbs tract\nThe goal of this talk is to discuss recent work\, joint with Doug C enzer\, on a notion of the extraction rate of Turing functionals that tran slate between notions of randomness with respect to different underlying p robability measures. We will analyze several classes of extraction proced ures: a first that generalizes von Neumann's trick for extracting unbiase d randomness from the tosses of a biased coin\, a second based on work of generating biased randomness from unbiased randomness by Knuth and Yao\, a nd a third independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For each of the above c lasses of extraction procedures\, we will identify a level of algorithmic randomness for an input that guarantees that we attain the corresponding e xtraction rate in producing an output. I will aim to present this materia l in a way that is accessible to logicians who are not specialists in comp utability theory / algorithmic randomness.\n LOCATION:https://stable.researchseminars.org/talk/OLS/4/ END:VEVENT END:VCALENDAR