Ravi Kannan receives ACM SIGACT Knuth Price 2011
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.
Prize. With a 'Z'.