Leonard Adleman

Last updated

Leonard Adleman
Len-mankin-pic.jpg
Born
Leonard Max Adleman

(1945-12-31) December 31, 1945 (age 78)
San Francisco, California, US
Alma mater University of California, Berkeley (BA, PhD)
Known for RSA
Awards Turing Award (2002)
Scientific career
Fields Computer science
Cryptography
Institutions University of Southern California
Thesis Number-Theoretic Aspects of Computational Complexity  (1976)
Doctoral advisor Manuel Blum

Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award. [1] He is also known for the creation of the field of DNA computing and coining the term computer virus. [2]

Contents

Biography

Leonard M. Adleman was born to a Jewish [3] family in California. His family had originally immigrated to the United States from modern-day Belarus, from the Minsk area. [3] He grew up in San Francisco and attended the University of California, Berkeley, where he received his B.A. degree in mathematics in 1968 and his Ph.D. degree in EECS in 1976. [1] [4] He was also the mathematical consultant on the movie Sneakers . [5] In 1996, he became a member of the National Academy of Engineering [6] for contributions to the theory of computation and cryptography. He is also a member of the National Academy of Sciences. [7]

Adleman is also an amateur boxer and has sparred with James Toney. [8]

Discovery

In 1994, his paper Molecular Computation of Solutions To Combinatorial Problems described the experimental use of DNA as a computational system. [9] In it, he solved a seven-node instance of the Hamiltonian Graph problem, an NP-complete problem similar to the travelling salesman problem. While the solution to a seven-node instance is trivial, this paper is the first known instance of the successful use of DNA to compute an algorithm. DNA computing has been shown to have potential as a means to solve several other large-scale combinatorial search problems. [10] Adleman is widely referred to as the Father of DNA Computing. [11]

In 2002, he and his research group managed to solve a 'nontrivial' problem using DNA computation. [12] Specifically, they solved a 20-variable SAT problem having more than 1 million potential solutions. They did it in a manner similar to the one Adleman used in his seminal 1994 paper. First, a mixture of DNA strands logically representative of the problem's solution space was synthesized. This mixture was then operated upon algorithmically using biochemical techniques to winnow out the 'incorrect' strands, leaving behind only those strands that 'satisfied' the problem. Analysis of the nucleotide sequence of these remaining strands revealed 'correct' solutions to the original problem. [1]

He is one of the original discoverers of the Adleman–Pomerance–Rumely primality test. [13] [14]

Fred Cohen, in his 1984 paper, Experiments with Computer Viruses credited Adleman with coining the term "computer virus". [15]

As of 2017, Adleman is working on the mathematical theory of Strata. He is a Computer Science professor at the University of Southern California. [16]

Awards

For his contribution to the invention of the RSA cryptosystem, Adleman, along with Ron Rivest and Adi Shamir, has been a recipient of the 1996 Paris Kanellakis Theory and Practice Award and the 2002 Turing Award, often called the Nobel Prize of Computer Science. [1] Adleman was elected a Fellow of the American Academy of Arts and Sciences in 2006 [17] and a 2021 ACM Fellow. [18]

See also

Related Research Articles

<span class="mw-page-title-main">Algorithm</span> Sequence of operations for a task

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences.

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">NP-hardness</span> Complexity class

In computational complexity theory, a computational problem H is called NP-hard if, for every problem L which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from L to H. That is, assuming a solution for H takes 1 unit time, H's solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class NP. As it is suspected, but unproven, that P≠NP, it is unlikely that any polynomial-time algorithms for NP-hard problems exist.

<span class="mw-page-title-main">Ron Rivest</span> American cryptographer

Ronald Linn Rivest is an American cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. He is an Institute Professor at the Massachusetts Institute of Technology (MIT), and a member of MIT's Department of Electrical Engineering and Computer Science and its Computer Science and Artificial Intelligence Laboratory.

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.

Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is the ACM Computing Classification System devised by the Association for Computing Machinery.

<span class="mw-page-title-main">DNA computing</span> Computing using molecular biology hardware

DNA computing is an emerging branch of unconventional computing which uses DNA, biochemistry, and molecular biology hardware, instead of the traditional electronic computing. Research and development in this area concerns theory, experiments, and applications of DNA computing. Although the field originally started with the demonstration of a computing application by Len Adleman in 1994, it has now been expanded to several other avenues such as the development of storage technologies, nanoscale imaging modalities, synthetic controllers and reaction networks, etc.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Jack Dongarra</span> American computer scientist (born 1950)

Jack Joseph Dongarra is an American computer scientist and mathematician. He is a University Distinguished Professor Emeritus of Computer Science in the Electrical Engineering and Computer Science Department at the University of Tennessee. He holds the position of a Distinguished Research Staff member in the Computer Science and Mathematics Division at Oak Ridge National Laboratory, Turing Fellowship in the School of Mathematics at the University of Manchester, and is an adjunct professor and teacher in the Computer Science Department at Rice University. He served as a faculty fellow at the Texas A&M University Institute for Advanced Study (2014–2018). Dongarra is the founding director of the Innovative Computing Laboratory at the University of Tennessee. He was the recipient of the Turing Award in 2021.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

<span class="mw-page-title-main">Leslie Valiant</span> British American computer scientist

Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

<span class="mw-page-title-main">Christos Papadimitriou</span> Greek-American computer scientist (b. 1949)

Christos Charilaos Papadimitriou is a Greek-American theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">Avi Wigderson</span> Israeli computer scientist and mathematician

Avi Wigderson is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, and distributed computing. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science. He also received the 2023 Turing Award for his contributions to the understanding of randomness in the theory of computation.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant such that the worst-case running time of the algorithm, on inputs of size , has an upper bound of the form

Natural computing, also called natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence, artificial immune systems, fractal geometry, artificial life, DNA computing, and quantum computing, among others.

Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.

References

  1. 1 2 3 4 "Leonard M. Adleman | American computer scientist". Encyclopædia Britannica. Retrieved 2015-11-24.
  2. ↑ "Professor Len Adleman explains how he coined the term "computer virus"". www.welivesecurity.com. Retrieved 2024-12-26.
  3. 1 2 Leonard (Len) Max Adleman 2002 Recipient of the ACM Turing Award Interviewed by Hugh Williams, August 18, 2016 amturing.acm.org
  4. ↑ Leonard Adleman at the Mathematics Genealogy Project
  5. ↑ "Sneakers". www.usc.edu. Archived from the original on 2015-11-01. Retrieved 2015-11-24.
  6. ↑ "NAE Website - Dr. Leonard M. Adleman". www.nae.edu. Retrieved 2015-11-24.
  7. ↑ "Leonard Adleman". www.nasonline.org. Retrieved 2015-11-24.
  8. ↑ Professor Adleman versus World Champion Boxer – YouTube
  9. ↑ "Adleman Papers". www.usc.edu. Archived from the original on 2016-03-04. Retrieved 2015-11-24.
  10. ↑ Adleman, Leonard M. (November 11, 1994). "Molecular Computation of Solutions to Combinatorial Problems" (PDF). Science. 266 (5187): 1021–1024. Bibcode:1994Sci...266.1021A. CiteSeerX   10.1.1.54.2565 . doi:10.1126/science.7973651. PMID   7973651. Archived from the original (PDF) on November 25, 2015.
  11. ↑ "Leonard Adleman".
  12. ↑ Braich, Ravinderjit S.; Chelyapov, Nickolas; Johnson, Cliff; Rothemund, Paul W. K.; Adleman, Leonard (2002-04-19). "Solution of a 20-Variable 3-SAT Problem on a DNA Computer". Science. 296 (5567): 499–502. Bibcode:2002Sci...296..499B. doi:10.1126/science.1069528. ISSN   0036-8075. PMID   11896237.
  13. ↑ Primality testing algorithms [after Adleman, Rumely and Williams], volume 901 of Lecture Notes in Mathematics. Springer Berlin. 1981.
  14. ↑ "NAE Website - DNA Computing by Self-Assembly". www.nae.edu. Retrieved 2015-11-24.
  15. ↑ Cohen, Fred (1984), Computer Viruses – Theory and Experiments
  16. ↑ "Adleman, Leonard - USC Viterbi Department of Computer Science". www.cs.usc.edu. Archived from the original on 2017-08-22. Retrieved 2017-08-22.
  17. ↑ "Book of Members, 1780-2010: Chapter A" (PDF). American Academy of Arts and Sciences. Retrieved 6 April 2011.
  18. ↑ "ACM Names 71 Fellows for Computing Advances that are Driving Innovation". Association for Computing Machinery. January 19, 2022. Retrieved 2022-01-19.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.