Seminar Event Detail


Logic

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.

Files:


Speaker:  Matthew Harrison-Trainor
Institution:  UM

Event Organizer:   Andreas R Blass    ablass@umich.edu

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.