Ravi Kannan Wins 2011 Knuth Prize

May 4, 2011

Ravi Kannan of Microsoft Research Labs will receive the ACM's 2011 Knuth Prize for developing algorithmic solutions to long-standing computational problems.

Kannan, who was a professor of computer science and of applied mathematics at Yale University and has taught at Carnegie Mellon University and MIT, has devised efficient algorithms overcoming mathematical and geometric problems in computer science. He has done research on lattices and their applications, machine learning, and computational linear algebra.

In a 1990 paper, Kannan, along with Martin Dyer (University of Leeds) and Alan Frieze (Carnegie Mellon University), showed how to efficiently produce estimates of the volumes of arbitrary high-dimensional convex sets. Their method used random walks on geometric sampling, a technique now central to the theory of algorithms. Winner of the Fulkerson Prize in Discrete Mathematics in 1991, the paper introduced the notion of geometric isoperimetry, a measure of an area marked by boundaries, to theoretical computer science.

In a 1991 paper, Kannan gave the first efficient algorithm to tackle the Frobenius problem, which seeks to find the largest number that cannot arise from a combination of certain denominations. His algorithm helped to develop integer programming and quantifier elimination. In a 1999 paper with Frieze, Kannan introduced the Weak Regularity Lemma, which is a combinatorial tool in sublinear algorithms, streaming algorithms, and graph limits.

The Knuth Prize—$5,000—is awarded every 18 months. Named for Donald Knuth of Stanford University, who has been called the "father of the analysis of algorithms," the prize will be presented at the ACM Symposium on Theory of Computing, on June 7, 2011, in San Jose, California.

Source: San Francisco Chronicle (April 26, 2011)