Ravindran Kannan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Ravi Kannan

Description de cette image, également commentée ci-après

Ravi Kannan sur sa page à l'université Yale

Naissance 12 mars 1953 (61 ans)
Chennai (Inde)
Domicile Bangalore
Champs 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[modifier | modifier le code]

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[modifier | modifier le code]

Domaines de recherche[modifier | modifier le code]

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 de programmation en nombre 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 (en), Kannan développe une version algorithmique du lemme de régularité (en) d'Endre 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 être représenté comme somme de nombres (de pièces) prises dans un ensemble donné. Par exemple, si 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,j \in \N). Dans ce cas simple de deux nombres a et b, une formule explicite simple a été donnée en 1884 par James Joseph Sylvester : le nombre de Frobenius est f = ab – a – b.

Contributions principales[modifier | modifier le code]

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

  • Martin Dyer (en), Alan M. Frieze et Ravindran Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, vol. 38, no 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)[modifier | modifier le code]

  • 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[modifier | modifier le code]

  • 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 technique algorithmique de grande portée en vue de résoudre des problèmes algorithmiques ouverts depuis longtemps »[3]..

Notes et références[modifier | modifier le code]

  1. Who's Who in Frontiers in Science and Technology 1985
  2. (en) Ravindran Kannan sur le site du Mathematics Genealogy Project.
  3. Microsoft Researcher to Receive ACM SIGACT Knuth Prize

Liens externes[modifier | modifier le code]