Special Colloquium
Matthew Harrison-Trainor
University of Michigan, Ann Arbor
Changing Information Content by Modifying the Source
Abstract: One of the applications of computability theory is to measure information content. I will talk about several theorems with a similar flavour, but in different contexts. Given some information source (e.g., a binary string) with some particular information content, how can we increase that information content by modifying the source? The first context will be algorithmic randomness, where the question takes the following form. Given a long binary string, in algorithmic randomness one measures the randomness of the string by dividing its Kolmogorov complexity by its length. By shortening the string (with advice) one can increase its randomness. We completely characterize how much one can increase the randomness. It turns out that this has connections to purely combinatorial questions of edge distribution in hypergraphs. The other two contexts will be introreducibility, which measures the redundancy of information, and coarse computability, which measures the "generic" information content modulo small errors.
Friday February 17, 2023 at 3:00 PM in 636 SEO