John T. Gill
# 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. Er wurde 1972 an der University of California, Berkeley, bei Manuel Blum promoviert (Probabilistic Turing Machines and Complexity of Computation). 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). Er führte in dieser Arbeit auch die probabilistischen Komplexitätsklassen BPP, ZPP und RP ein.

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.

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

