“Understanding Science Through the Lens of Computation”
Dr. Richard M. Karp
The University of California at Berkeley
Friday, April 3, 11 a.m.
TI Auditorium (ECS South 2.102)
Abstract
Viewing natural or engineered systems through the lens of their computational requirements or capabilities provides new insights and ways of thinking about computational processes. In this lecture I will briefly describe how a computational viewpoint illuminates several areas, including biology, sociology, economics, quantum computing, statistical physics, the Web and the Internet.
Biological processes at many levels can be understood in terms of computation. These range from the molecular level to the operation of the immune system and the brain, and to the behavior of ant colonies, beehives and birds flying in formation. In the social sciences, the strategic behavior of companies can be approached algorithmically using tools such as computational game theory, and the evolution of Web-based social networks can be cast in algorithmic terms. Although the Web and the Internet are man-made, they were not really designed and can best be understood as natural phenomena. The behavior of computational devices at a subatomic level leads to the abstract mathematical model of a quantum computer. Researchers in quantum computation study the computational potential of this model, and in the process devise new tests of the validity of the standard theory of quantum mechanics. Statistical physics is based on stochastic models of the interaction of large assemblages of atoms, molecules or molecular spins, and finds common ground with stochastic models in computer science involving the interactions of large numbers of combinatorial variables and constraints, or the interactions of many agents communicating and negotiating over the Internet.
Biography
Richard M. Karp received his Ph.D. from Harvard in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at IBM Research. From 1968 to 1994 and from 1999 to the present he has been a professor at the University of California, Berkeley, where he is a University Professor. From 1988 to 1995 and 1999 to the present he has been a research scientist at the International Computer Science Institute in Berkeley. From 1995 to 1999 he was a professor at the University of Washington. During the 1999-2000 academic years he was the Hewlett-Packard Visiting Professor at the Mathematical Sciences Research Institute.
The unifying theme in Dr. Karp's work has been the study of combinatorial algorithms. His 1972 paper, “Reducibility Among Combinatorial Problems,” showed that many of the most commonly studied combinatorial problems are NP-complete and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking, and he has supervised 36 Ph.D. dissertations.
His honors and awards include: the U.S. National Medal of Science, the Turing Award, the Fulkerson Prize, the Harvey Prize (Technion), the Centennial Medal (Harvard), the Lanchester Prize, the Von Neumann Theory Prize, the Von Neumann Lectureship, the Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), the Babbage Prize and eight honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science.
