Ravindran Kannan

Main contributions are efficient algorithms which exploit the mathematical structure of problems. With coauthors Dyer and Frieze, he devised the first polynomial time bounded algorithm for the classical problem of estimating the volume of a high dimensional convex set for which they received the Fulkerson Prize. This work has applications to multivariate integration and probability estimation. He did extensive work on matrix algorithms. Sampling to reduce the size of problems that need to be solved is essential for large matrix problems. With coauthors introduced techniques for sampling on the fly for such problems. Their research was widely applied and extended by many researchers over the last 15 or so years. His earlier papers proving lower bounds on Boolean circuit size have turned out to have numerous applications. His work on lattice algorithms, especially the solution of the long-standing Frobenius coin problem, is mathematically bold and interesting.