Berkeleyan
Richard Karp, computer theorist, awarded 2008 Kyoto Prize
| 17 July 2008
Richard Karp, a professor of electrical engineering and computer sciences, has been named a laureate of the 2008 Kyoto Prize, Japan’s equivalent of the Nobel Prize, in recognition of his lifetime achievements in the field of computer theory.
 |
 Richard Karp (Peg Skorpinski photo) |
Karp, 73, was one of three laureates announced in June by the Inamori Foundation, which awards the Kyoto Prize annually to those who have contributed significantly to the betterment of humanity in the categories of advanced technology, basic sciences, and arts and philosophy.
Karp, a University Professor with joint appointments in mathematics, bioengineering, and industrial engineering and operations research, is being honored in the advanced technology category, which focuses on information science. (The title University Professor, given by the UC regents, is reserved for scholars of international distinction who are recognized and respected teachers with exceptional ability.)
Each laureate will receive a diploma, a Kyoto Prize Medal of 20-carat gold, and a cash gift of 50 million yen (approximately $460,000) during a week of ceremonies beginning Nov. 9. On March 18, 2009, the laureates will assemble in San Diego for three days to participate in the eighth annual Kyoto Laureate Symposium.
“I’m very honored by this recognition, not only for myself but for the field that I work in, which I think is of great value to society,” said Karp in a recent interview with the Inamori Foundation.
Considered one of the world’s leading computer theorists, Karp, who also holds a position as a senior research scientist at the International Computer Science Institute in Berkeley, significantly advanced the theory of NP-completeness conceived in 1971 by former Berkeley math professor Stephen Cook.
The Inamori Foundation credited Karp’s work on NP-completeness for developing a standard method for characterizing combinatorial problems into classes and identifying their level of intractability. Those that are “NP-complete” are the most difficult to solve. “Karp’s theory streamlined algorithm design for problem-solving, accelerated algorithm engineering, and brought computational complexity within the scope of scientific research,” according to a statement by the Inamori Foundation.
NP-completeness theory has become a cornerstone of modern theoretical computer science. In the 1980s, for their contributions to the concept of NP-completeness, Cook and Karp each received the Turing Award, the highest honor given in the field of computer science.
More recently, Karp has applied his talents to the field of bioinformatics and computational biology, where computers and algorithms are used to analyze and model data to determine how genes and living cells work. He has developed algorithms for constructing various kinds of physical maps of DNA targets, and methods for classifying biological samples on the basis of gene expression data. His current interests are in the application of combinatorial and probabilistic methods to finding hidden patterns in gene-expression data and discovering the structure of genetic regulatory networks.
The Kyoto Prize is the latest in a string of awards earned by Karp. Among the honors he has received (in addition to the Turing Award) are a U.S. National Medal of Science, Fulkerson Prize, Von Neumann Theory Prize, UC Berkeley Distinguished Teaching Award, and eight honorary degrees.