Ravi Kannan
Ravindran Kannan , called Ravi, (born March 12, 1953 in Madras ) is an Indian computer scientist and mathematician.
Life
Kannan studied at the Indian Institute of Technology Bombay and received his PhD in 1980 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 , was a professor at Carnegie Mellon University in the 1990s and then at Yale University . He is currently Principal Research Scientist at Microsoft Research in India (where he leads the Algorithms Research Group) and teaches at the Indian Institute of Science in Bangalore .
plant
With Alan M. Frieze he found an algorithmic version of the regularity lemma by Endre Szemerédi . In their work they introduced the weak regularity lemma, which has become an important combinatorial tool for various algorithms (streaming algorithms, graph limits, sublinear algorithms).
In 2011 he received the Knuth Prize for the development of influential algorithmic methods for solving long-open computation problems with applications to the processing of large amounts of data, making fundamental contributions in very different areas of computer science such as lattices and their applications, geometric algorithms, machine learning and numerical linear algebra performed. He also dealt with Markov chains and their mixing times, clustering.
In 1991 he received the Fulkerson Prize with Martin Dyer and Frieze for a polynomial-time algorithm for calculating the volume of any convex body.
Also in 1991 he solved Frobenius' coin problem and gave an efficient (polynomial time) algorithm to determine the Frobenius number. The problem named after Ferdinand Georg Frobenius asks for the largest number that cannot be generated from n given numbers by addition (this number is the Frobenius number).
With Frieze and Santosh Vempala, he investigated low-order approximations to matrices.
Together with John E. Hopcroft he is working on a book Computer Science Theory for the Information Age , the preliminary version of which is available online.
In 2002 he was invited speaker at the International Congress of Mathematicians in Beijing (Rapid mixing in Markov chains). In 2015 he was elected to the American Academy of Arts and Sciences and in 2016 a Fellow of the Association for Computing Machinery .
Web links
- Site at Microsoft Research (English)
Individual evidence
- ^ Biographical data according to Marquis, Who´s Who in Frontiers in Science and Technology 1985
- ↑ Ravi Kannan in the Mathematics Genealogy Project (English)
- ↑ Frieze, Kannan: The regularity lemma and approximation schemes for dense problems , Proc. 37th Symposium Foundations of Computer Science (FOCS) 1996. Frieze, Kannan: A simple algorithm for constructing Szemeredis regularity partition , Electronic J. Combinatorics, Volume 6, 1999
- ↑ SIGACT, Appreciation for the Knuth Prize 2011 ( Memento of the original from April 29, 2011 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.
- ↑ Frieze, Petros Drineas, Kannan, Vempala, V. Vinay: Clustering in large graphs and matrices , Symposium on Discrete Algorithms (SODA) 1999
- ^ For: Martin E. Dyer, Alan M. Frieze and Ravindran Kannan: A random polynomial time algorithm for approximating the volume of convex bodies , Journal of the ACM, Vol. 38, 1991, pp. 1-17
- ↑ Kannan: Lattice translates of a polytope and the Frobenius problem , Combinatorica, Volume 12, 1992, pp. 161-177
- ↑ Frieze, Kannan, Vempala: Fast Monte Carlo algorithms for finding low rank approximants , Proc. FOCS 1998
- ^ John E. Hopcroft, Ravi Kannan, Foundations of Data Science, 2014, pdf
| personal data | |
|---|---|
| SURNAME | Kannan, Ravi |
| ALTERNATIVE NAMES | Kannan, Ravindran |
| BRIEF DESCRIPTION | Indian computer scientist |
| DATE OF BIRTH | March 12, 1953 |
| PLACE OF BIRTH | Madras |