Ravindran Kannan

Ses intérêts en recherche comprennent l'algorithmique, l'informatique théorique et les mathématiques discrètes ainsi que l'optimisation. Ses travaux se concentrent sur le développement d'algorithmes efficaces pour des problèmes de nature mathématique, et souvent géométriques, qui apparaissent en informatique. Il a travaillé sur des algorithmes d'optimisation linéaire en nombres entiers, la géométrie des nombres, les marches aléatoires dans des espaces de dimension arbitraire, les algorithmes randomisés pour l'algèbre linéaire et des algorithmes d'apprentissage pour des ensembles convexes.

Avec Alan M. Frieze, Kannan développe une version algorithmique du « lemme de régularité de Szemerédi ». Ils introduisent un lemme de régularité faible qui devient un outil combinatoire important pour divers types d'algorithmes (algorithme de fouille de flots de données, limites de graphes, algorithmes sous-linéaires).

En 1991, Kannan publie un algorithme efficace (c'est-à-dire en temps polynomial) pour résoudre le « problème des pièces de monnaie », aussi appelé « problème de Frobenius » : il s'agit de déterminer le plus grand entier (appelé nombre de Frobenius) qui ne peut pas être représenté comme somme de nombres pris dans un ensemble donné. Par exemple, si l'on possède des pièces de valeur unitaire 3 et 5, le nombre de Frobenius est 7 : tout entier n plus grand peut être écrit sous la forme n = 3i + 5j (avec i et j entiers naturels). Dans ce cas simple de deux nombres a et b, une formule explicite, souvent attribuée à tort à Sylvester, fait partie du folklore mathématique (en) : le nombre de Frobenius est ab – a – b.

Parmi ses contributions principales qui lui ont valu les prix dont il est lauréat figurent :

• Martin Dyer, Alan M. Frieze et Ravindran Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, vol. 38, n^o 1,‎ 1991, p. 1-17
• Alan M. Frieze et Ravindran Kannan, « A Simple Algorithm for Constructing Szemerédi's Regularity Partition », Electronic Journal of Combinatorics, vol. 6,‎ 1999 (lire en ligne) Cet article est présenté au Symposium FOCS en 1966 sous le titre The regularity lemma and approximation schemes for dense problems.

• Ravindran Kannan et László Lovász, « Covering Minima and lattice point free convex bodies », Annals of Mathematics, vol. 128,‎ 1988, p. 577–602
• Ravindran Kannan, « Lattice translates of a polytope and the Frobenius problem », Combinatorica, vol. 12,‎ 1992, p. 161-177
• A. Blum (en), Alan M. Frieze, Ravindran Kannan et S. Vempala, « A Polynomial-Time Algorithm for learning noisy linear threshold functions », Algorithmica, vol. 22,‎ 1998, p. 35–52
• P. Drineas, Alan M. Frieze, Ravindran Kannan, S. Vempala et V. Vinay, « Clustering in large graphs and matrices », Proceedings of the Symposium on Discrete Algorithm,‎ 1999