Gary L. Miller

Données clés
Résidence	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].

Travaux et distinctions

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 apporté des contributions significatives au problème de l'isomorphisme de graphes, en identifiant des classes 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

Il est fait ACM Fellow en 2002^[2].
En 2003, il est lauréat du prix Paris Kanellakis de l'Association for Computing Machinery avec Michael O. Rabin, Robert Solovay et Volker Strassen, pour le test de primalité de Miller-Rabin.
Il obtient le prix Donald E. Knuth en 2013^[1].

Notes et références

↑ ^{a b et c} Annonce ACM du prix 2013 « Copie archivée » (version du 23 juillet 2018 sur Internet Archive).
↑ Citation pour la nomination de Gary Miller comme ACM Fellow.

(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

Riemann's Hypothesis and Tests for Primality. Texte de la thèse de Ph. D.
Page personnelle de Gary Miller à Carnegie Mellon.
Ressources relatives à la recherche :

Portail de l'informatique théorique

[ACM-1] {a b et c} Annonce ACM du prix 2013 « Copie archivée » (version du 23 juillet 2018 sur Internet Archive).

[2] Citation pour la nomination de Gary Miller comme ACM Fellow.

[1]

[2]