John T. Gill

John T. Gill (John Thomas Gill, III ) ist ein US-amerikanischer Informatiker und Hochschullehrer an der Stanford University.

Gill ist afroamerikanischer Herkunft und studierte Physik und Chemie am Georgia Institute of Technology.[1] Er wurde 1972 an der University of California, Berkeley, bei Manuel Blum promoviert (Probabilistic Turing Machines and Complexity of Computation).[2] Er ist Associate Professor an der Stanford University.

Er befasst sich mit theoretischer Informatik (Komplexitätstheorie, probabilistischem Rechnen, Informationstheorie, Fehlerkorrigierende Codes, Datenkompression), insbesondere Zusammenhang von Berechenbarkeitstheorie und Wahrscheinlichkeit sowie Informationstheorie, speziell verlustlose Datenkompression. Insbesondere führte er mehrere probabilistische Komplexitätsklassen ein.

1977 führte er die Komplexitätsklasse Probabilistische Polynomialzeit ein (PP).[3] Er führte in dieser Arbeit auch die probabilistischen Komplexitätsklassen BPP, ZPP und RP ein.[4]

Gill arbeitete nicht nur rein theoretisch, er hat auch große praktische Erfahrung mit realen Computersystemen. Anfang der 1980er Jahre war er an der Entwicklung der MIPS-Architektur beteiligt als Teil des Entwicklungsteams.[1]

Er schlug Martin Hellman die Verwendung des diskreten Logarithmus für seinen Public-Key-Kryptographie-System (Diffie-Hellman-Schlüsselaustausch) vor.[1]

Einzelnachweise

  1. ↑ a b c John T. Gill III, Adinkra Research Project
  2. ↑ John T. Gill im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
  3. ↑ Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, Band 6, 1977, S. 675–695.
  4. ↑ Siehe die Einträge in Complexity Zoo
Personendaten
NAME Gill, John T.
ALTERNATIVNAMEN Gill, John Thomas III (vollständiger Name)
KURZBESCHREIBUNG US-amerikanischer Mathematiker
GEBURTSDATUM vor 1972