Pure and Applied Mathematics
Applied the theory of Kolmogorov complexity
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.