The 2011 Knuth Prize is awarded to Ravindran (Ravi) Kannan of Microsoft Research Labs India, Adjunct Professor of International Centre for Theoretical Sciences - TIFR, Adjunct Professor at Indian Institute of Science and formerly on the faculty at Yale, Carnegie- Mellon, and MIT.
The citation for the prize is: For more than 30 years, Ravi has provided theoretical computer science with many powerful new algorithmic techniques, which have enhanced our understanding of computational complexity, discrete mathematics, geometry, and operations research. His work is deep and fundamental.
Ravi's work spans many subfields of theoretical computer science, including algorithmic geometry of numbers, randomized algorithms, computational linear algebra, lower bounds, and machine learning. In all of these subfields, his contributions have been foundational. Among his many and varied results, we cite four in particular.
- The celebrated Frobenius problem from algorithmic geometry of numbers, asks for the largest natural number that is not expressible as a nonnegative integer combination of a given set of natural numbers. This was a long-standing open problem. In his 1991 paper "Lattice translates of a polytope and the Frobenius problem", Ravi presented a polynomial-time algorithm for this problem for every fixed-size set of numbers. Ravi's solution led to important developments in integer programming and quantier elimination.
- Ravi's 1991 paper with Dyer and Frieze, "A random polynomial-time algorithm for estimating the volumes of convex bodies", contains the first polynomial-time algorithm for estimating the volume of a convex body to an arbitrary accuracy. This paper has been called "one of the most remarkable algorithmic achievements ever", and was awarded a Fulkerson Prize in 1991. The paper originated the use of rapidly mixing random walks in high-dimensional convex bodies, and also introduced the notion of geometric isoperimetry to theoretical computer science. Ravi subsequently produced many more breakthroughs involving geometric sampling in highdimensions, a technique that is now central to the theory of algorithms.
- In his 1998 paper with Frieze and Vempala, "Fast Monte-Carlo algorithms for finding low rank approximations", he provided a constant-time randomized approximation scheme for singular-value decomposition of a matrix. By sampling, they reduced the problem to one involving a very small matrix whose singular values approximate those of the original matrix. This work is relevant to principal component analysis.
- In his 1999 paper with Frieze, "Quick approximation to matrices and applications", he introduced the Weak Regularity Lemma, which says that every graph can be "approximated" by an object of "complexity" that depends only on the quality of the approximation and not on the size of the original graph. This lemma has become an important new combinatorial tool in several areas, including sublinear algorithms, streaming algorithms, and graph limits.
These are only four examples; the depth and breadth of Ravi's contributions to the field are astounding.
Ravi has been called a "fantastic mentor" to his younger collaborators. He has also been an inspiration to many other researchers. For all of these reasons, he is highly deserving of this Prize.