AMMCS-2011 Plenary Talk:

Kolmogorov complexity and its applications in computer science

by Ming Li

University of Waterloo

Computer Science, as a science of information processing, has risen as a major disclipline during the past half century. Along with it, a new mathematical theory -- Kolmogorov complexity --- has emerged. In this talk, we will explain two applications of Kolmogorov complexity in computer science.

The first application is on the average-case analysis of algorithms. In computer science, analyzing the average behavior of an algorithm is a difficult task as, by definition, it involves averaging over all inputs. It would make the average-case analysis easy if we could find a "typical input" which causes the program run in the "average-case". Such a typical input can never be found but it exists according to Kolmogorov complexity. We will demonstrate how to use this fact to give an average case analysis of ShellSort, partially solving an open question of 40 years; and to give a very simple proof of Lovasz Local Lemma.

The second application is on how to measure information distance between any two information carrying entities. This optimal metric has been successfully applied to measure the distances between two genomes, two chain letters, two images, two programs, a query and an answer on the internet, and many other applications.

Ming Li is a Canada Research Chair in Bioinformatics and a University Professor at the University of Waterloo. He is a fellow of the Royal Society of Canada, ACM, and IEEE. He is a recipient of E.W.R. Steacie Fellowship Award in 1996, the 2001 Killam Fellowship, and the 2010 Killam Prize. Together with Paul Vitanyi they have co-authored the book "An Introduction to Kolmogorov Complexity and Its Applications". He is a co-managing editor of Journal of Bioinformatics and Computational Biology. He is an associate editor-in-Chief of Journal of Computer Science and Technology.