Richard J. Lipton

from Wikipedia, the free encyclopedia

Richard Jay Lipton (born September 6, 1946 ) is an American computer scientist (theoretical computer science, cryptology , DNA computer ).

Lipton studied at Case Western Reserve University with a bachelor's degree in 1968 and received his PhD in 1973 with David Parnas at Carnegie Mellon University (On Synchronization Primitive Systems). He then taught at Yale University , from 1978 at the University of California, Berkeley , 1980 to 2000 at Princeton University and from 2000 at the Georgia Institute of Technology .

Among other things, he dealt with verification of programs, security of databases, parallel algorithms, game theory, multi-party communication protocols and theoretically with DNA computing, where he is considered one of the pioneers with Leonard Adleman . He showed that DNA computers can solve some difficult computational problems like the SAT problem for Boolean circuits.

With Richard M. Karp in 1980 he proved Karp and Lipton's theorem in the satisfiability problem of propositional logic (SAT). He was a consulting scientist at Telcordia (formerly Bellcore) from 1996 and headed a laboratory at Panasonic . He was a Guggenheim Fellow (1981), is a Fellow of the Association for Computing Machinery and the National Academy of Engineering . In 2014 he received the Knuth Prize and was accepted into the American Academy of Arts and Sciences .

He has his own blog Gödel's lost letter and P = NP and published articles from it in 2010 as a book.

His PhD students included Avi Wigderson and Dan Boneh .

Fonts

  • The P = NP Problem and Gödel's Lost Letter, Springer Verlag 2010

Web links

Individual evidence

  1. ^ Richard J. Lipton in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  2. ^ Lipton DNA solution of hard computational problems , Science, 268, 2010, 542-545
  3. ↑ Boneh, Dunworth, Lipton, Sgall On the computational power of DNA , Discrete Applied Mathematics, Volume 71, 1996, pp. 79-94
  4. ↑ Karp, Lipton Some connections between nonuniform and uniform complexity classes , Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, 1980, pp. 302-309
personal data
SURNAME Lipton, Richard J.
ALTERNATIVE NAMES Lipton, Richard Jay (full name)
BRIEF DESCRIPTION American computer scientist
DATE OF BIRTH September 6, 1946