Richard J. Lipton

US-amerikanischer Informatiker
(Weitergeleitet von Richard Lipton)

Richard Jay Lipton (* 6. September 1946) ist ein US-amerikanischer Informatiker (Theoretische Informatik, Kryptologie, DNA-Computer).

Lipton studierte an der Case Western Reserve University mit dem Bachelor-Abschluss 1968 und wurde 1973 bei David Parnas an der Carnegie Mellon University promoviert (On Synchronization Primitive Systems).[1] Danach lehrte er an der Yale University, ab 1978 an der University of California, Berkeley, 1980 bis 2000 an der Princeton University und ab 2000 am Georgia Institute of Technology, wo er zuletzt Frederick G. Story Professor of Computing war und nun emeritiert ist.[2]

Er befasste sich unter anderem mit Verifikation von Programmen, Sicherheit von Datenbanken, Parallelalgorithmen, Spieltheorie, Vielparteien-Kommunikationsprotokolle und theoretisch mit DNA-Computing, wo er mit Leonard Adleman als einer der Pioniere gilt. Er zeigte, dass DNA-Computer einige schwierige Rechenprobleme[3] lösen können wie das SAT-Problem für Boolesche Schaltkreise.[4]

Mit Richard M. Karp bewies er 1980 den Satz von Karp und Lipton im Erfüllbarkeitsproblem der Aussagenlogik (SAT).[5] Er war ab 1996 beratender Wissenschaftler bei Telcordia (dem ehemaligen Bellcore) und leitete ein Labor bei Panasonic. Er war Guggenheim Fellow (1981), ist Fellow der Association for Computing Machinery und der National Academy of Engineering. 2014 erhielt er den Knuth-Preis[6] und wurde in die American Academy of Arts and Sciences aufgenommen.[7]

Zusammen mit seinem Kollegen Kenneth W. Regan betreibt er das Blog Gödel´s lost letter and P=NP. Er veröffentlichte Beiträge daraus 2010 als Buch.

Zu seinen 20 Doktoranden gehörten Avi Wigderson und Dan Boneh.[8]

Schriften

Bearbeiten
  • The P=NP Problem and Gödel´s Lost Letter. Springer Verlag, 2010, ISBN 978-1-4419-7154-8.
  • mit Kenneth W. Regan: Introduction to Quantum Algorithms Via Linear Algebra. 2. Auflage. MIT Press, 2021, ISBN 978-0-262-04525-4 (Erstausgabe: 2014).
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Richard J. Lipton im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
  2. Dick Lipton. In: College of Computing, Georgia Tech. Abgerufen am 26. November 2023 (englisch).
  3. Lipton DNA solution of hard computational problems, Science, 268, 2010, 542–545
  4. Boneh, Dunworth, Lipton, Sgall On the computational power of DNA, Discrete Applied Mathematics, Band 71, 1996, S. 79–94
  5. Karp, Lipton Some connections between nonuniform and uniform complexity classes, Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, 1980, S. 302–309
  6. ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory. In: acm.org. 15. September 2014, abgerufen am 26. November 2023 (englisch).
  7. Lipton Elected to American Academy of Arts and Sciences. In: gatech.edu. 29. April 2014, abgerufen am 26. November 2023 (englisch).
  8. Richard Jay Lipton. In: Mathematics Genealogy Project. Abgerufen am 26. November 2023.