Gary L. Miller

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

Gary L. Miller

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

Gary Miller (à gauche) avec Volker Strassen

Domicile Pittsburgh
Institutions Université Carnegie-Mellon
Directeur de thèse Manuel Blum
Étudiants en thèse Susan Landau, Tom Leighton, Shang-Hua Teng, Jonathan Shewchuk
Renommé pour Test de primalité de Miller-Rabin
Distinctions Prix Paris Kanellakis (2003), Prix Knuth (2013)

Gary Lee Miller est un professeur d'informatique à l'université Carnegie-Mellon, à Pittsburgh, aux États-Unis. Miller a obtenu un Ph.D. de l'université de Californie à Berkeley en 1975 sous la direction de Manuel Blum. Sa thèse de Ph.D. est intitulée Riemann's Hypothesis and Tests for Primality. Ensuite, il a été en poste à l'université de Waterloo, à l'université de Rochester à New York, au Massachusetts Institute of Technology, et à l'Université de Caroline du Sud avant d'être nommé à Carnegie-Mellon[1].

Le test de primalité présenté par Gary Miller en 1975 est le premier algorithme de test dont l'efficacité est prouvée, mais son efficacité est conditionnée par la véracité de l'hypothèse de Riemann qui, elle, n'est toujours pas prouvée. En 1976, Michael O. Rabin montre que par randomisation, on peut contourner l'hypothèse non prouvée. Le nouvel algorithme, appelé test de primalité de Miller-Rabin, est maintenant employé dans la pratique, par exemple pour la génération de clés dans l'algorithme de chiffrement RSA. Pour ce travail, Miller et Rabin constituent, avec Robert Solovay et Volker Strassen, le groupe des lauréats du prix Paris Kanellakis de 2003.

Miller a aussi fait des contributions significatives au problème de l'isomorphisme de graphes, en identifiant des classe particulières où une solution efficace existe. Miller a traité, avec John Reif, le cas de graphes dont le genre et la valence sont bornés. Également avec John Reif, il conçoit la notion de « contraction parallèle d'arbres », qui est devenue une primitive fondamentale dans la conception d'algorithmes parallèles, avec de multiples application à des problèmes algébriques et de théorie des graphes.

En 1984, Miller change de domaine et travaille dans le domaine de l'analyse numérique, et plus généralement de calcul scientifique. Il s'intéresse aux algorithmes de maillage, et obtient, en 2010, avec Ioannis Koutis et Richard Peng, des résultats innovants qui aboutissent à l'algorithme le plus rapide connu, en théorie et en pratique, pour la résolution de systèmes linéaires symétriques à diagonale dominante. Ces systèmes interviennent en traitement d'image, algorithmique des réseaux, ingénierie informatique et simulation informatique de phénomènes physiques[1].

Prix et distinctions[modifier | modifier le code]

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gary Miller (computer scientist) » (voir la liste des auteurs)

Liens externes[modifier | modifier le code]