[cs-talks] Upcoming CS Seminars: Theory Seminar (Fri)
fgreen1 at bu.edu
Mon Nov 2 11:31:09 EST 2015
Kolmogorov complexity -- a randomized approximation of the shortest description
Peter Gacs, BU
Friday, November 6, 2015 at 12pm in MCS 135
ABSTRACT: The Kolmogorov complexity K(x) of a binary string x of length n is the length of the shortest code from which a certain fixed universal machine can compute x. This function is uncomputable, there is not even any way to compute a non-constant lower bound to K(x).
And a shortest code does not seem too useful: the time it takes to recover x from it cannot be bounded by any computable function of n. Surprisingly, however, it is possible to find with good probability a short list of strings containing a near-optimal code for x. More precisely, there is a randomized polynomial algorithm that produces a list of length n that with probability 1-\delta contains a code for x whose size differs from K(x) by at most O(\log^2(n/\delta)). So -- in some sense — compression can be done efficiently, even if decompression may take a non-computable amount of time. This result, the work of several people (not including me), relies on a modification of certain (expander-like) graphs called extractors.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cs-talks