Featured ICSI Researcher: Richard Karp

Richard Karp wears too many hats for one title to apply. He has appointments in UC Berkeley's departments of Electrical Engineering and Computer Science, Mathematics, Bioengineering, and Operations Research. He's the head and founder of ICSI's Algorithms Group (originally the Theory Group), and a member of the Networking Group. His interests span optimization, genomic modeling, and applied research.

"The problems almost always involve the design of combinatorial algorithms," Karp says.

Born in Boston, Massachusetts, the son of a junior high school math teacher, Karp was educated at the Boston Latin School and Harvard University. After receiving his PhD in 1959, Karp began working at IBM in Yorktown Heights, New York, where, he says, "Most of the time I could just play around." At night, he taught evening courses at colleges around New York.

Karp then left IBM to become a professor at UC Berkeley. "This was during the 1960s, when it seemed more fun to be in Berkeley than anywhere else," he said. "It was a very pleasant culture shock." He remembers colleagues being jailed for participation in the protests, and having to hold classes in his home when political protests shut the campus down

He has been with ICSI since 1988, when the Institute opened for business. As the Algorithms Group leader, he supervises researchers from all over the world interested in a wide cross–section of topics related to theoretical algorithms. In the 2009 to 2010 academic year, nearly half of his group were postdoctoral Fellows sponsored by the German Academic Exchange Service. He also collaborates closely with researchers in and from Israel, which, he says, accounts for 20 percent of the world's activity in theoretical computer science.

Besides four years at the University of Washington, Karp has been at UC Berkeley since 1968, where he has earned a reputation as an excellent teacher. He was awarded a Distinguished Teaching Award from UC Berkeley.

"Teaching is first of all a lot of fun," he says. "It makes you rethink your work, and when you have to give a lecture on an idea, it forces you to understand it."

Even after decades of research, Karp is continually refining and rethinking his ideas. He's always been interested in puzzles and random choices, but when he took an undergraduate course at Harvard University in probability theory, he turned his attention in that direction. While a graduate student, he studied computational methods for solving optimization problems in industry. He's particularly interested in discrete mathematics. His research at IBM was mainly in algorithmic linear programming, in which the mathematician tries to find the best outcome for a problem given a series of constraints.

He eventually began to study computational complexity theory, and in 1972 published the landmark paper "Reducibility Among Combinatorial Problems." In that paper, he showed that some algorithms problems can be impossibly difficult to solve. He's interested in "why we can solve these problems even though complexity theory tells us it's impossibly hard." In awarding him the Turing Award in 1985, the ACM cited Karp for introducing the "now standard methodology for proving problems to be computationally difficult."

In the early 1990s, with the advent of the Human Genome Project, Karp became interested in applying combinatorial and probabilistic algorithms to biological problems. Much of the work today of ICSI's Algorithms Group focuses on answers to biological questions.

In recent years, he has returned to heuristic algorithms, algorithms which make sense intuitively but not theoretically, and problems related to machine learning. He has also become more and more interested in specific problems, rather than theories as a whole — for example, in looking at actual computer runs.

Over the years, his intellectual flexibility and groundbreaking research have brought him numerous accolades — including, notably, the Turing Award and the Kyoto Prize, which is described as the Japanese Nobel Prize. But for Karp, research is as much a process of failing as it is of succeeding — of trying different approaches over and over again without any guarantee of success.

He says, "Enjoy your failures as much as your successes, because they will be much more numerous."