Randomness extraction from a computability-theoretic perspective

Abstract: The goal of this talk is to discuss recent work, joint with Doug Cenzer, on a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We will analyze several classes of extraction procedures: a first that generalizes von Neumann's trick for extracting unbiased randomness from the tosses of a biased coin, a second based on work of generating biased randomness from unbiased randomness by Knuth and Yao, and a third independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For each of the above classes of extraction procedures, we will identify a level of algorithmic randomness for an input that guarantees that we attain the corresponding extraction rate in producing an output. I will aim to present this material in a way that is accessible to logicians who are not specialists in computability theory / algorithmic randomness.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic