Colloquium Speaker

Speaker:		Tao Jiang McMaster University Hamilton, Ontario, Canada
Topic:		Average-case Analysis by the Incompressibility Method
Date:		Tuesday, March 23, 1999
Time:		9:30 AM
Place:		Gould-Simpson, Room 701

ABSTRACT

A string $x$ is said to be incompressible if the shortest algorithmic description of $x$ (which is also called the Kolmogorov complexity of $x$) has length at least $|x|$. Strings that are incompressible are patternless since a pattern could be used to reduce the description length. The incompressibility method is an elementary yet powerful proof technique based on the fact that most strings are incompressible. It has been used successfully in many areas including lower bounds for computational models, formal language and automata theory, combinatorics, and average-case analysis of algorithms. In a typical proof using the incompressibility method, one first chooses an incompressible object from the class under discussion. The argument invariably says that if a desired property does not hold for this object, then the object can be compressed. This yields the required contradiction. Furthermore, since most objects are incompressible, the desired property usually holds on average.

In this talk, we first give a brief exposition of Kolmogorov complexity and the incompressibility method, and then focus on the application of the method in average-case analysis. The examples considered here include some well-known sorting algorithms.

This is joint work with Ming Li and Paul Vitanyi.