Date: Thursday, November 18, 2021
Location: 2866 East Hall (4:00 PM to 5:30 PM)
Title: Boosting the information density of binary strings
Abstract: This is a continuation of last week's talk, dealing with the graph theory question mentioned at the end of the abstract:
Given a binary string s, we can measure the information content of s using Kolmogorov complexity. The information density of s is the Kolmogorov complexity of s divided by the length of s. We will consider the problem of producing, from a string s, a shorter string s' of higher information density than s ("extracting" the complexity from s). In fact we cannot do this, but we can produce two shorter strings s' and s'' such that one of the two will have higher information density than s. I will talk about this problem, which turns out to be equivalent to a purely graphtheoretic problem about how spread out the edges in a graph can be.
Files:
Speaker: Matthew HarrisonTrainor
Institution: UM
Event Organizer: Andreas R Blass ablass@umich.edu
