Loading AI tools
informaticien américain De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir Gary Miller et Miller.
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].
| 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) |
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
