Gary L. Miller

Gary L. Miller Beskrivelse af dette billede, kommenteres også nedenfor Gary Miller (til venstre) med Volker Strassen

Nøgledata
Hjem Pittsburgh
Institutioner Carnegie-Mellon University
Tilsynsførende Manuel Blum
Ph.d.-studerende Susan Landau, Tom Leighton, Shang-Hua Teng , Jonathan Shewchuk
Berømt for Miller-Rabin primality test
Priser Paris Kanellakis-pris (2003), Knuth-pris (2013)

Gary Lee Miller er professor i datalogi ved Carnegie-Mellon University , Pittsburgh , USA . Miller fik en ph.d. fra University of California i Berkeley i 1975 under vejledning af Manuel Blum . Hans ph.d.-afhandling har titlen Riemann's Hypothesis and Tests for Primality . Derefter tjente han ved University of Waterloo , University of Rochester i New York, Massachusetts Institute of Technology og University of South Carolina, før han blev udnævnt til Carnegie-Mellon.

Værker og udmærkelser

Primalitetstesten præsenteret af Gary Miller i 1975 er den første testalgoritme, hvis effektivitet er blevet bevist, men dens effektivitet er betinget af sandheden i Riemann-hypotesen , som stadig ikke er bevist. I 1976 viser Michael O. Rabin , at ved randomisering kan vi omgå den uprøvede hypotese. Den nye algoritme, kaldet Miller-Rabin-test , bruges nu i praksis for eksempel til nøglegenerering i RSA-krypteringsalgoritmen . Til dette arbejde udgør Miller og Rabin sammen med Robert Solovay og Volker Strassen gruppen af ​​vindere af Paris Kanellakis-prisen i 2003 .

Miller yder også betydelige bidrag til grafens isomorfismeproblem og identificerer bestemte klasser, hvor der findes en effektiv løsning. Miller har behandlet tilfældet med grafer, hvis slægt og valens er afgrænset med John Reif. Også hos John Reif udtænkte han forestillingen om "parallel sammentrækning af træer", som er blevet en grundlæggende primitiv i designet af parallelle algoritmer med flere anvendelser til algebraiske problemer og grafteori.

I 1984 skiftede Miller felt og arbejdede inden for numerisk analyse og mere generelt inden for videnskabelig beregning. Han er interesseret i mesh- algoritmer og opnår i 2010 sammen med Ioannis Koutis og Richard Peng innovative resultater, der fører til den hurtigste kendte algoritme, i teorien og i praksis, til opløsning af lineære systemer symmetrisk til dominerende diagonal . Disse systemer er involveret i billedbehandling , algoritmer til netværk , computerteknik og computersimulering af fysiske fænomener.

Præmier og anerkendelse

Noter og referencer

  1. ACM-meddelelse om prisen "Arkiveret kopi" 2013 (version dateret 23. juli 2018 på internetarkivet ) .
  2. Henvisning til Gary Millers nominering som ACM-stipendiat .
(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen "  Gary Miller (computerforsker)  " ( se forfatterlisten ) .

eksterne links