George Barmpalias: Compression of data streams down to their information content

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 7 November 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: George Barmpalias

Title: Compression of data streams down to their information content


According to Kolmogorov complexity, every finite binary string is
compressible to a shortest code – its information content – from
which it is effectively recoverable. We investigate the extent to
which this holds for infinite binary sequences (streams). We devise a
new coding method which uniformly codes every stream X into an
algorithmically random stream Y, in such a way that the first n bits
of X are recoverable from the first I(X[1..n]) bits of Y, where I is any
partial computable information content measure which is defined on all
prefixes of X, and where X[1..n] is the initial segment of X of
length n. As a consequence, if g is any computable upper bound on the
initial segment prefix-free complexity of X, then X is computable from
an algorithmically random Y with oracle-use at most g. Alternatively
(making no use of such a computable bound g) one can achieve an
oracle-use bounded above by K(X[1..n])+log(n). This provides a strong
analogue of Shannon’s source coding theorem for algorithmic
information theory.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.