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 *