Ravindran Kannan

Données clés
Naissance	12 mars 1953 (71 ans); Chennai (Inde)
Résidence	Bangalore
Domaines	Informatique
Diplôme	Université Cornell
Directeur de thèse	Leslie Earl Trotter
Distinctions	Prix Fulkerson (1991); Prix Knuth (2011),

Ravindran Kannan, appelé Ravi, né le 12 mars 1953 à Chennai^[1] est un informaticien et mathématicien. Il est chercheur principal (Principal Researcher) chez Microsoft Research Inde, où il dirige le groupe de recherche en algorithmique. Il est aussi premier adjoint de la faculté d'informatique et du département d'automation à l'Indian Institute of Science de Bangalore.

Biographie

Kannan a fait ses études supérieures à l'Institut indien de technologie de Bombay et a obtenu un Ph.D. à l'université Cornell, en 1980, sous la direction de Leslie Earl Trotter, intitulée The size of numbers in the analysis of certain algorithms^[2]. Il a enseigné au Massachusetts Institute of Technology, puis a été professeur à l'université Carnegie-Mellon, et ensuite professeur d'informatique et de mathématiques appliquées à l'université Yale sur la chaire William K. Lanman Jr. et il rejoint enfin Microsoft.

Recherche

Domaines de recherche

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.

Contributions principales

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.

Autres publications (sélection)

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

Prix et récompenses

Distinguished Alumnus award de l'Institut indien de technologie de Bombay en 1999.
Conférencier invité au Symposium Foundations of Computer Science de l'IEEE en 1997.
Lauréat du Prix Fulkerson 1991 en mathématiques discrètes avec Martin Dyer et Alan M. Frieze pour leur article sur le volume d'ensembles convexes cité ci-dessus.
Ravi Kannan est lauréat du prix Knuth 2011 qui lui est attribué « pour avoir développé des techniques algorithmiques de grande portée en vue de résoudre des problèmes algorithmiques ouverts depuis longtemps »^[3]..