|Volume 7, Issue 1 -
Richard M. Karp
Throughout his long and distinguished career, Richard M. Karp has made major contributions to the fields of computer science, mathematics, operations research, statistics, engineering, and molecular biology, with the unifying theme being the study of combinational algorithms. "After more than four decades and exposure to countless algorithms, I continue to find the subject full of surprises and mysteries," he says.
Karp received his Ph.D. in Applied Mathematics from Harvard University in 1959. His dissertation was based on the idea that the flow of control in a computer program can be represented by a directed graph, and that graph theory algorithms can be used to analyze programs. "In a loose sense, this work was a precursor of the later development in the field of code optimization," he says.
Karp then joined the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center, where he worked until 1968. "To my great good fortune, IBM Research became a mecca for combinatorial mathematicians during the early 1960s," he says. "Although computers were primitive by today's standards, they could already be used to solve logistical problems of significant size. Splendid algorithms for linear programming and network flow problems had been discovered, and the field of combinatorial algorithms was in a stage of rapid development."
Karp decided to leave IBM for the University of California (U.C.) Berkeley, where he was a Professor of Computer Science, Mathematics, and Operations Research from 1968 to 1994. "I moved to Berkeley to lead a more rounded life than the somewhat isolated suburban environment of IBM could provide. One aspect of this was the desire to be more involved with students," he says. "I have been involved in teaching throughout my career and have always enjoyed it."
Throughout his years at Berkeley, Karp supervised 35 Ph.D. students and continued to conduct groundbreaking research in combinational algorithms and other related areas. Of his many achievements, Karp's most significant work is considered to be in the 1972 paper, "Reducibility Among Combinatorial Problems," which shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. Much of his subsequent work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems, and the construction of randomized algorithms for combinatorial problems.
Karp has conducted extensive research and authored numerous articles in the field of parallel computation. "One major theme in this work has been the continuing quest for a formal model of parallel computation that is simple enough for theoretical studies and yet can serve as a guide for designing and predicting the performance of parallel algorithms," he says. Karp's research in this area has also focused on the powerful role of randomization in the construction of efficient parallel algorithms, the proof of lower bounds on the complexity of parallel computation, and the recognition that communication is the limiting resource in most applications of parallel processing. He has worked on systolic algorithms,asynchronous parallel computation, algorithms for shared-memory machines, parallel combinatorial search and, most recently, The LogP model, which seeks to capture the key performance characteristics of the current generation of distributed-memory machines.
In 1988, Karp was part of a group of Berkeley faculty members who helped establish the International Science Institute (ICSI). Its theoretical computer science group attracted postdocs and visitors from around the world. In 1995, Karp retired from U.C. Berkeley and worked at ICSI before accepting a faculty position at the University of Washington (UW), where he is currently a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology.
"I was attracted by the congenial atmosphere and strong colleagues in the computer science department at UW, and by the strength and depth of the activity in molecular biology, led by Lee Hood." says Karp. "Hood saw the sequencing of genomes as merely a first step towards the era of 'functional genomics,' in which the complex regulatory networks that control the functioning of cells and systems such as the immune system would be understood through a combination of large-scale automated experimentation and subtle algorithms. I decided that nothing else I might work on could be more important than computational biology and its application to functional genomics."
Karp's current research is concerned with strategies for sequencing the human genome, the physical mapping of large DNA molecules, the analysis of gene expression data, and other combinatorial problems arising in molecular biology. "I have found that the basic logic of experimentation in molecular biology can, to some extent, be codified in abstract terms, and I have discovered that the task of inferring the structure of genomes and regulatory networks can lead to interesting combinatorial problems," he says. "Typically, the truth emerges in stages through an interplay between computation and experimentation, in which inconsistencies in experimental data are discovered through computation and corrected by further experimentation."
Karp has received numerous honors and awards throughout his career, including the U.S. National Medal of Science, the Turing Award, the Fulkerson Prize, the von Neumann Theory Prize, the Lanchester Prize, the von Neumann Lectureship, and the Distinguished Teaching Award at U.C. Berkeley. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Philosophical Society, as well as a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.
Reflecting on his long and enriching career as a renowned scientist and
teacher, Karp says, "Being a professor at a research university is the best
job in the world. It provides a degree of personal autonomy that no other
profession can match, the opportunity to serve as a mentor and role model
for talented students, and an environment that encourages and
supports work at the frontier of emerging areas of science and technology.
I am fortunate to have come along at a time when such a career path has