Ravindran Kannan
Encyclopedia
Ravindran Kannan is currently a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science
. Before joining Microsoft, he was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University
. He has also taught at MIT and CMU
. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2011 Knuth Prize
to Ravi Kannan for developing influential algorithmic techniques aimed at solving long-standing computational problems.
Ravi Kannan did his B.Tech at IIT, Bombay and PhD. at Cornell University
. His research interests include Algorithms, Theoretical Computer Science and Discrete Mathematics as well as Optimization. His work has mainly focused on efficient algorithms
for problems of a mathematical (often geometric) flavor that arise in Computer Science. He has worked on algorithms for integer programming
and the geometry of numbers
, random walks in n-space
, randomized algorithm
s for linear algebra
and learning algorithms for convex set
s.
(1) – Polynomial-time algorithm for approximating the volume of convex bodies
(2) – Algorithmic version for Szemerédi regularity partition
"A Polynomial-Time Algorithm for learning noisy Linear Threshold functions," with A. Blum, A. Frieze and S. Vempala, Algorithmica
22:35–52, 1998.
"Covering Minima and lattice point free convex bodies," with L. Lovász, Annals of Mathematics
, 128:577–602, 1988.
from the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). He is the joint winner of the 1991 Fulkerson Prize
in Discrete Mathematics
for his work on the volumes of convex
bodies. He is a Distinguished Alumnus of IIT Bombay.
Indian Institute of Science
Indian Institute of Science is a research institution of higher learning located in Bangalore, India. It was established in 1909.-History:After a chance meeting between Jamsetji N...
. Before joining Microsoft, he was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University
Yale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
. He has also taught at MIT and CMU
CMU
CMU may stand for a university:*Carnegie Mellon University in Pittsburgh, Pennsylvania, United States*Central Michigan University in Mount Pleasant, Michigan, United States*Canadian Mennonite University in Winnipeg, Manitoba, Canada...
. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2011 Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
to Ravi Kannan for developing influential algorithmic techniques aimed at solving long-standing computational problems.
Ravi Kannan did his B.Tech at IIT, Bombay and PhD. at Cornell University
Cornell University
Cornell University is an Ivy League university located in Ithaca, New York, United States. It is a private land-grant university, receiving annual funding from the State of New York for certain educational missions...
. His research interests include Algorithms, Theoretical Computer Science and Discrete Mathematics as well as Optimization. His work has mainly focused on efficient algorithms
for problems of a mathematical (often geometric) flavor that arise in Computer Science. He has worked on algorithms for integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
and the geometry of numbers
Geometry of numbers
In number theory, the geometry of numbers studies convex bodies and integer vectors in n-dimensional space. The geometry of numbers was initiated by ....
, random walks in n-space
N-Space
n-Space is an American video game developer founded in 1994 by Erick S. Dyke, Dan O'Leary, and Sean Purcell. n-Space is focusing mostly on Nintendo consoles since 2001...
, randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s for linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
and learning algorithms for convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s.
Key contributions
Among his many contributions, two are(1) – Polynomial-time algorithm for approximating the volume of convex bodies
Polynomial-time algorithm for approximating the volume of convex bodies
The paperis a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan.The main result of the paper is a randomized algorithm for finding an \epsilon approximation to the volume of a convex body K in n-dimensional Euclidean space by assume the existence of a membership oracle...
(2) – Algorithmic version for Szemerédi regularity partition
Algorithmic version for Szemerédi regularity partition
A Simple Algorithm for Constructing Szemerédi's Regularity Partition is a paper by Alan M. Frieze and Ravi Kannan giving an algorithmic version of the Szemerédi regularity lemma to find an ε-regular partition of a given graph....
Other representative publications
"Clustering in large graphs and matrices," with P. Drineas, A. Frieze, S. Vempala and V. Vinay, Proceedings of the Symposium on Discrete Algorithms, 1999."A Polynomial-Time Algorithm for learning noisy Linear Threshold functions," with A. Blum, A. Frieze and S. Vempala, Algorithmica
Algorithmica
Algorithmica is a monthly computer science journal, published by Springer New York. It includes both theoretical papers on algorithms addressing problems arising in practical areas and experimental papers covering practical aspects or techniques....
22:35–52, 1998.
"Covering Minima and lattice point free convex bodies," with L. Lovász, Annals of Mathematics
Annals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...
, 128:577–602, 1988.
Awards and honors
Ravi Kannan will receive the 2011 Knuth PrizeKnuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
from the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). He is the joint winner of the 1991 Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
in Discrete Mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
for his work on the volumes of convex
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
bodies. He is a Distinguished Alumnus of IIT Bombay.
See also
- Szemerédi regularity lemmaSzemerédi regularity lemmaIn mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove ...
- Alan M. FriezeAlan M. FriezeAlan M. Frieze is a professor in the Department of Mathematical Sciences at Carnegie Mellon University, Pittsburgh, United States. He graduated from the University of Oxford in 1966, and obtained his PhD from the University of London in 1975. His research interests lie in combinatorics, discrete...
- Avrim BlumAvrim BlumAvrim Blum is a prominent computer scientist who in 2007 was inducted as a Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms."-Biography:...
- László LovászLászló LovászLászló Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....