[cs-talks] Upcoming CS Seminars: Theory Seminar (Fri)

Greenwald, Faith fgreen1 at bu.edu
Mon Nov 2 11:31:09 EST 2015

Theory Seminar
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...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20151102/5d73eb43/attachment.html>

More information about the cs-talks mailing list