Browse Theses

While complexity theory studies the difficulty of solving all instances of a given problem with a single program, Kolmogorov complexity is a much more local measure of complexity. The Kolmogorov complexity of a string measures the length of the smallest single-purpose program whose sole task is to print out that string. This can be thought of as a measure of the amount of randomness in any given string.

The interplay between the two areas of research occurs on many levels. Kolmogorov complexity can be used as a proof technique to solve problems in complexity theory, or it can be viewed as an independent and complementary approach to complexity. The results in this thesis illustrate the diversity of relationships between the two.

The contributions of this thesis fall into three categories.

First, we give results in which Kolmogorov complexity is used as a proof technique to obtain lower bounds for the number of rounds required in a bare-bones variant of self-reducibility.

Second, we study the relationship between Kolmogorov complexity and extractors. Extractors are graphs with certain "uniformity" properties; they are a very effective tool for reducing the amount of randomness required by randomized algorithms. Our results show how they can be used to obtain upper bounds in a time-bounded variant of Kolmogorov complexity. Bounds of this kind are known to apply to several important results in complexity. We also show, using similar ideas, how to "distill" Kolmogorov complexity efficiently.

Finally, we give a new Kolmogorov-based measure of the complexity of distinguishing strings. At first glance, this measure may appear to be too localized to yield any information on the more global, standard approach to complexity. However it provides a very different perspective on complexity, and yields very general lower bounds in one model of communication complexity.