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 graph-theoretic problem about how spread out the edges in a graph can be. Speaker(s): Matthew Harrison-Trainor (UM)