On Kolmogorov Complexity

This semester I assisted to a course on Kolmogorov Complexity and Minimum Description Length, given at the Institute for Logic, Language and Computation of the University of Amsterdam.
The main lecturer, Paul Vitanyi, is the c0-author of THE book on Kolmogorov Complexity. Peter Gr├╝nwald, invited professor in two lectures, is the author of THE book on the Miniumum Description Length principle. The exercise sessions were given by a talented PhD student of them, Wouter Koolen-Wijkstra.

But what is this all about?
In simple words, the Kolmogorov Complexity of a sequence of characters is the length of the shortest program that outputs that sequence. It is the theoretical limit of compression.

Leave a Reply

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

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current month ye@r day *