Gary L. Miller

Gary L. Miller Descrizione di questa immagine, commentata anche di seguito Gary Miller (a sinistra) con Volker Strassen

Dati chiave
Casa Pittsburgh
Istituzioni Università Carnegie Mellon
Supervisore Manuel Blum
Studenti di dottorato Susan Landau, Tom Leighton, Shang-Hua Teng , Jonathan Shewchuk
Rinomato per la Test di primalità di Miller-Rabin
Premi Premio Paris Kanellakis (2003), Premio Knuth (2013)

Gary Lee Miller è un professore di informatica alla Carnegie-Mellon University , Pittsburgh , Stati Uniti . Miller ha conseguito un dottorato di ricerca presso l' Università della California a Berkeley nel 1975 sotto la supervisione di Manuel Blum . La sua tesi di dottorato è intitolata Ipotesi di Riemann e test per la primalità . Ha poi prestato servizio presso l' Università di Waterloo , l' Università di Rochester a New York, il Massachusetts Institute of Technology e l' Università della Carolina del Sud prima di essere nominato alla Carnegie-Mellon.

Opere e distinzioni

Il test di primalità presentato da Gary Miller nel 1975 è il primo algoritmo di test la cui efficacia è stata dimostrata, ma la sua efficacia è condizionata dalla veridicità dell'ipotesi di Riemann , che ancora non è provata. Nel 1976, Michael O. Rabin ha dimostrato che mediante la randomizzazione , possiamo aggirare l'ipotesi non dimostrata. Il nuovo algoritmo, chiamato test di primalità di Miller-Rabin , viene ora utilizzato nella pratica, ad esempio per la generazione di chiavi nell'algoritmo di crittografia RSA . Per questo lavoro, Miller e Rabin, insieme a Robert Solovay e Volker Strassen , formano il gruppo dei vincitori del Paris Kanellakis Prize 2003 .

Miller ha anche dato un contributo significativo al problema dell'isomorfismo del grafo , identificando classi particolari in cui esiste una soluzione efficiente. Miller ha trattato, con John Reif, il caso di grafi il cui genere e valenza sono delimitati. Sempre con John Reif, concepisce la nozione di "contrazione parallela degli alberi", che è diventata una primitiva fondamentale nella progettazione di algoritmi paralleli, con molteplici applicazioni a problemi algebrici e teoria dei grafi.

Nel 1984, Miller ha cambiato campo e ha lavorato nel campo dell'analisi numerica e più in generale del calcolo scientifico. Si interessa di algoritmi mesh , e ottiene, nel 2010, con Ioannis Koutis e Richard Peng, risultati innovativi che portano all'algoritmo più veloce conosciuto, in teoria e in pratica, per la risoluzione di sistemi lineari simmetrici alla diagonale dominante . Questi sistemi sono coinvolti nell'elaborazione delle immagini , negli algoritmi per le reti , nell'ingegneria informatica e nella simulazione al computer di fenomeni fisici.

Premi e riconoscimenti

Note e riferimenti

  1. Annuncio ACM del 2013 premio "archiviati Copy" (versione del 23 luglio 2018 l' Internet Archive ) .
  2. Citazione per la nomina di Gary Miller come ACM Fellow .
(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato "  Gary Miller (informatico)  " ( vedere l'elenco degli autori ) .

link esterno