|Date: Thursday, November 11, 2021
Location: 2866 East Hall (4:00 PM to 5:30 PM)
Title: Boosting the information density of binary strings
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 graph-theoretic problem about how spread out the edges in a graph can be.
Speaker: Matthew Harrison-Trainor
Event Organizer: Andreas R Blass firstname.lastname@example.org