Tuesday, April 26, 2011

Ravi Kannan wins the Knuth Prize

Ravi Kannan will receive the 2011 Knuth Prize for his algorithmic work, including approximating volumes of high-dimensional convex objects, computing the Frobenius number and finding low-rank approximations to matrices. The techniques Kannan helped develop, including sampling via random walks and the weak regularity lemma, have applications across the algorithmic spectrum.

Kannan will receive his award at the STOC conference at this year's FCRC meeting the week of June 5th. He will give the Knuth Prize lecture as an FCRC plenary speaker. With Les Valiant's Turing Award lecture on Sunday and Ravi Kannan's Knuth Prize lecture Tuesday, not to mention STOC (with the first STOC poster session), Complexity, EC and many other conferences, San Jose is the place to be in June. Early registration deadline is May 16.


  1. Congratulations, well deserved! Many of the works mentioned are joint with Alan Frieze... Any idea why he was not a co-winner?

  2. To Anon: The Knuth prize is always given to a single individual. It is good to keep in mind for any award that no research is ever done on an island, always done with or built on great work of others.

  3. Congratulations to Ravi! Why is Knuth prize not awarded to young Computer Science researchers? It seems they pick only the 50+ year olds.