Kolmogorov Complexity and Its Applications

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

Kolmogorov complexity is a modern theory of randomness and has many applications in computer science and other fields. The investigator is enriching this theory and its applications by doing research in two directions. Analyzing the average-case complexity of an algorithm is at the heart of practical algorithm analysis. It has been demonstrated over the past decade that Kolmogorov complexity is a powerful tool to help analyzing the average-case complexity and the lower bounds of algorithms. Examples are the average case analysis of Shellsort and Heapsort. The PI plans to continue this work to systematically develop the tool, the Incompressibility Method. This involves comparative studies to understand why, how, and when the incompressibility method works. In order to demonstrate, and to uncover, the power of this method, this method will be used to solve other open questions. Samples of some open questions include: improving Shellsort average-case lower bound analysis, average height of balanced trees, and Stack sorting lower bound. The modern information age and the post-genomic era raises a fundamental question: Given two sequences (genomes or English documents), how much information do they share? For example, given two genomes, can we measure their evolutionary distance? The goal of this second part of the proposal is to understand this fundamental question and develop tools. In the past, the PI and his coauthors have partially answered this question by defining the concept of Information Distance. Information Distance measures the absolute thermodynamic energy required to convert one sequence to another. However, it does not measure evolutionary distance because genomic evolution allows long segment deletion/insertion, cheaply. A new theory suitable for such evolutionary distance will be developed. To demonstrate the feasibility of this research, some preliminary theory has been proposed and successfully applied to construct whole genome and chain letter phylogenies when no other method applies. More recently, this theory has also been applied to program plagiarism detection and language classification.