Knuth Prize 2011 Goes to Microsoft Researcher
Written by Sue Gee   
Thursday, 28 April 2011

Ravi Kannan has been named as the winner of of the 2011 Knuth Prize, awarded annually by the Special Interest Group on Algorithms and Computation Theory of the ACM (Association for Computing Machinery).

 

The ACM Algorithms and Computation Theory group has awarded this year's Knuth Prize to Ravi Kannan of Microsoft Research Labs India for

"developing influential algorithmic techniques aimed at solving long-standing computational problems."

Much of the work that is cited as the reason for awarding the prize might seem very abstract  but there are also some very practical areas of research.

 

kannan

 

The main paper that is cited presents an algorithm that runs in polynomial time for estimating the volume of a convex body in n dimensional space. It makes use of a random walk on the convex body generated by a type of Markov chain.  A large part of Kannan's work is about random algorithms using Markov chains.

Another more practical area of research is the application of mostly random algorithms to big data and sampling.  For example a fast Monte Carlo algorithm that produces an approximate matrix multiplication has all sorts of practical applications. Clustering algorithms also figure in the research, as do lattice algorithms.

Overall the focus of the research is on algorithms and as such Kannan is a good choice for this prize which is associated with the father of the analysis of algorithms, Donald Knuth.

More Information

ACM's announcement of award

Ravi Kannan's home page where you will find PDFs of all of his papers.

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

 

Banner


Atlas In Action With Reinforcement Learning
21/03/2025

A new video from Boston Dynamics and the Robotics and AI (RAI) Institute show the impact reinforcement learning has had on Atlas's fluidity of movement and demos what can be achieved by combining the  [ ... ]



Time To Change The Clocks
30/03/2025

This is the time of year when the clocks change to provide us with daylight saving and a significant trauma. The time is ripe to think of innovative clocks and one thing about clocks is that they suit [ ... ]


More News

espbook

 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Friday, 17 August 2018 )