Ravindran Kannan
Ravindran Kannan, called Ravi, ( born March 12, 1953 in Madras) is an Indian computer scientists and mathematicians.
Life
Kannan studied at the Indian Institute of Technology Bombay in 1980 and his doctorate from Cornell University with Leslie Earl Trotter (The size of numbers in the analysis of Certain algorithms ). He taught at the Massachusetts Institute of Technology, in the 1990s, was a professor at Carnegie Mellon University and then at Yale University. He is currently a Principal Research Scientist at Microsoft Research in India ( where he leads the research group for algorithms) and teaches at the Indian Institute of Science, Bangalore.
Work
By Alan M. Frieze, he found an algorithmic version of the regularity lemma of Szemerédi Endre. In their work, they introduced the weak regularity lemma, which was an important combinatorial tool for various algorithms (Streaming Algorithms, Graph Limits, Sublinear Algorithms ).
In 2011 he was awarded the Knuth Prize for developing influential algorithmic methods for solving long open computational problems with applications to process large amounts of data, which he made fundamental contributions in many different areas of computer science such as grid and its applications, geometric algorithms, machine learning and numerical linear algebra made. He also dealt with Markov chains and their mixing times, clustering.
In 1991 he was awarded the Fulkerson Prize with Martin Dyer and Frieze for a polynomzeitlichen algorithm to calculate the volume of any convex body.
Also in 1991 he solved the Frobenius problem and gave an efficient ( polynomzeitlichen ) algorithm for determining the Frobenius number. Named after Ferdinand Georg Frobenius problem (also called coin problem ) asks for the largest number that can not be generated from n given numbers by addition ( this number is the Frobeniuszahl ). If one chooses, for example, in the case of n = 2 as the base of coins 3 and 5, the Frobeniuszahl 7, in the case n = 2, there is even a simple formula for the Frobeniuszahl found in 1884 by James Joseph Sylvester (whether the base number of a, b, then the Frobeniuszahl f = a - a - b), n is greater than 2 but is not such a simple formula known.
With Frieze and Santosh Vempala, he investigated low rank approximations of matrices.
Together with John E. Hopcroft he is working on a book Computer Science Theory for the Information Age, the pre-release version can be accessed online.
In 2002 he was invited speaker at the International Congress of Mathematicians in Beijing (Rapid mixing in Markov chains ).