Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ


Choose your language

InfoQ Homepage News Ravi Kannan receives ACM SIGACT Knuth Price 2011

Ravi Kannan receives ACM SIGACT Knuth Price 2011

This item in japanese


 Ravi Kannan from Microsoft Research has been appointed winner of the ACM SIGACT's (Special Interest Group on Algorithms and Computation Theory) Knuth Price 2011. According to the press announcement the scientist from Microsoft Research receives the price for his work on

influential algorithic techniques aimed at solving long-standing computational problems.

He will give his Knuth Price Lecture at the ACM Symposium on Theory of Computing.

Many software engineers might assume, that that there are only few problems left for researchers with respect to algorithms. Libraries such as those for computer graphics or numeric computations are hidden in the guts of the implementation. However, some essential problems are still hard to solve or require efficient approaches. Ravi 's activities at the Microsoft Research Labs in Bangalore (India) focuses on various fields such as theoretical computer science, geometric algorithms, machine learning, and computational linear algebra. The research group was founded in 2007 in order to focus on 21st Century Algorithms which seek to address the new demands in today’s environment of computing with massive data.

As an example, ACM calls one of Ravi's research papers which has been published in 1990, one of the most remarkable algorithmic achievements ever:

A random polynomial-time algorithm for approximating the volume of convex bodies, written with Martin Dyer of the University of Leeds and Alan Frieze of Carnegie Mellon University, shows how to efficiently produce estimates of the volumes of arbitrary high-dimensional convex sets. The method they developed uses random walks to do geometric sampling, a technique now central to the theory of algorithms. The winner of the Fulkerson Prize in Discrete Mathematics in 1991, this paper also introduced the notion of geometric isoperimetry, a measure of an area marked by boundaries, to theoretical computer science.

Readers who want to dive deeper into Ravi's work, should take a look at his home page.




Rate this Article


Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Community comments

  • Prize. With a 'Z'.

    by Austin Mills,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    The Knuth price is $2.56, the amount he sends to you as a reward for finding a typo in his books.

  • Re: Prize. With a 'Z'.

    by Michael Stal,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    Guess, this is another Knuth Award :-)

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p