SCS DISTINGUISHED LECTURE SERIES
Combinatorial Optimization as a Tool for Molecular Biology
Thursday, 11 September 1997
4:00 pm, Wean Hall 7500
3:45 pm - Refreshments Outside Wean Hall 7500
SPEAKER BIO
Richard M. Karp was born in Boston, Massachusetts in 1935 and was
educated at the Boston Latin School and Harvard University, where he
received the Ph.D. in Applied Mathematics in 1959. From 1959 to 1968
he was a member of the Mathematical Sciences Department at the IBM
Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor
of Computer Science, Mathematics and Operations Research at the
University of California, Berkeley. From 1988 to 1995 he was also
associated with the International Computer Science Institute in
Berkeley. In 1995 he became a Professor of Computer Science and
Engineering and an Adjunct Professor of Molecular Biotechnology at the
University of Washington.
The unifying theme in Karp's work has been the study of combinatorial
algorithms. His most significant work is 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. His 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.
Karp has received the U.S. National Medal of Science, the Turing Award
(ACM) the Fulkerson Prize(AMS and Math. Programming Society), the von
Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von
Neumann Lectureship (SIAM) and the Distinguished Teaching Award
(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.