# 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."