Past Winner
1996 E.W.R. Steacie Memorial Fellowship

Ming Li

Computer Science

University of Waterloo

When computer scientist Ming Li was doing his Ph.D. at Cornell University in the early 1980s, his advisor, Juris Hartmanis, gave him several papers to read on "Kolmogorov complexity." He put them away. One year later, Dr. Li realized that this theory of randomness, first formulated about 30 years ago, could provide the breakthrough for a problem he was trying to solve. It did, and so began his deep fascination with the theory.

Dr. Li, now a professor at the University of Waterloo, is playing a key role in developing and demonstrating the power of Kolmogorov complexity. His book (co-authored with Paul Vitányi), An Introduction to Kolmogorov Complexity and Its Applications, was the first comprehensive book in this field. It is used to teach graduate seminar courses all over the world; various parts of the book have been translated into Chinese, Japanese and Russian. Drs. Li and Vitányi's work has changed the status of Kolmogorov complexity - from elegant idea to versatile tool for concrete investigations.

The power of Kolmogorov complexity is that it allows scientists to quantify the randomness of individual objects in an objective and absolute manner. This is impossible using classical probability theory. For example, in computer science it is often necessary to determine how fast a certain program runs. Using conventional methods, this is very difficult because the program must be run with a large number of inputs, each result analyzed, and an average time arrived at. Using Kolmogorov complexity, only one input is needed to complete the analysis.

In one area of his current research (which also includes machine learning and computational biology), Dr. Li is extending the use of Kolmogorov complexity in the analysis of computer programs, DNA sequence analysis, physics and computation. Others are following his lead. "Since our book came out in 1993, I've been hearing from researchers who have been inspired to use Kolmogorov complexity - from philosophers working on inductive inference to marine scientists trying to use it to measure the complexity of dolphin sounds," Dr. Li says. "This is a powerful idea. There are few applications that would surprise me."