Ming Li Pure and Applied Mathematics

Applied the theory of Kolmogorov complexity

The Story

Li is playing a key role in developing and demonstrating the power of Kolmogorov complexity, a theory of randomness. The Kolmogorov complexity of an object is how briefly it can be described. It has applications in programming, artificial intelligence, information theory, statistics, and related fields. Li's 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. 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), Li is extending the use of Kolmogorov complexity in the analysis of computer programs, DNA sequencing, physics and computation. Others are following his lead.

Source: NSERC

Career ideas:

  • Mathematicians
  • Statisticians
  • Systems analysts
  • Computer programmers
  • Accountants
  • Actuarians
  • Financial auditors
  • Insurance analysts
  • Teachers
  • Investment analysts
  • Financial planners

The Person

Hong Kong
Waterloo, ON
Computer Scientist; Professor
Department of Computer Science, University of Waterloo, Ontario
  • PhD, Cornell University, New York
  • Steacie Memorial Fellowship, 1996
Last Updated
December 26, 2011

Personal Webpage

Profile viewed 36640 times

Other scientists who may be of interest: