Professor Richard Karp has led ICSI’s Algorithms Group for the majority of its existence since 1988. Dick has just been named the founding director of an institute that will host research on theoretical computer science and its outreach to other scientific fields. The Simons Institute for the Theory of Computing will be funded by a $60 million grant to UC Berkeley from the Simons Foundation.

Dick is a university professor of electrical engineering and computer science at UC Berkeley and has additional appointments in the Mathematics, Bioengineering, and Industrial Engineering and Operations Research Departments. He is perhaps best known for his work in computational complexity theory, in which he showed that some algorithms problems can be impossibly difficult to solve, but over the years, his focus, and that of his research group, has gradually shifted from theoretical algorithms to algorithms for real-world problems. The group now performs extensive statistical research on the correlation between diseases and genetic variation.

Of particular interest to Dick – and the motivation for establishing the Simons institute – is how theoretical computer science can shed light on “processes in nature which are typically studied in terms of physical transformation and energy, but which at their core can be abstracted as algorithms.”

Computational Complexity

Dick was born in Boston, Massachusetts, and received a classical education at the Boston Latin School. He’s always been interested in games and puzzles, an interest that sharpened when he took a course in probability theory as an undergraduate at Harvard. As a graduate student, he developed computational methods for solving optimization problems in industry and received his PhD from Harvard in 1959.

He then took a research position at IBM in Yorktown Heights, New York, where, he says, “Most of the time I could just play around.” There, he focused on combinatorial algorithms, optimization, and parallel computation. At night, he taught evening courses at colleges around New York.

In 1968, Dick left IBM to become a professor in UC Berkeley’s departments of computer science and industrial engineering and operations research. “This was during the 1960s, when it seemed more fun to be in Berkeley than anywhere else,” he said. He saw protests held and colleagues jailed; when the campus shut down, classes met in Dick’s home. “It was a very pleasant culture shock.”

He began to study computational complexity theory and in 1972 published the groundbreaking paper “Reducibility Among Combinatorial Problems.” There, he showed that some algorithms problems can be impossibly difficult to solve in all cases. He’s interested in “why we can solve these problems in practice even though complexity theory tells us it’s impossibly hard.” In presenting him with the Turing Award in 1985, the ACM cited Dick for introducing the “now standard methodology for proving problems to be computationally difficult.”

In the years leading up to ICSI’s formation, he was appointed the associate chair of the Computer Science Department and a professor of mathematics at UC Berkeley. He also served as the co-chair of the computational complexity program at the Mathematical Sciences Research Institute in Berkeley.

At ICSI

In 1986, the German Federal Laboratory for Computer Science chose Berkeley as the site for a new institution that would strengthen ties between the computer science communities of Germany and the U.S. Dick was one of five UC Berkeley computer science professors who developed the Institute’s bylaws and fleshed out its affiliation with the university. He was also appointed to the first Board of Trustees when ICSI was incorporated in July 1986.

By 1988, ICSI’s research groups had been established. Dick was the first member of the Theory Group, later renamed the Algorithms Group. Other than the four years he spent at the University of Washington, he has led the group since then.

In its first ten years, the Algorithms Group had especially productive collaborations with foreign researchers. The group has had – and continues to have – many German postdoctoral fellows on ICSI’s visiting program and collaborations with researchers from Israel, which, Dick says, accounts for 20 percent of the world’s activity in theoretical computer science. An Israeli researcher, Amos Fiat, worked with Dick and Michael Luby on one of the group’s first major accomplishments in the late 1980s. They developed a solution to the paging problem, in which a cache – a system’s short-term memory – must decide what data to delete in order to make room for more data. A perfect algorithm would know the future and never delete data that will be requested. Algorithms in the real world have no such luxury. Some algorithms delete data in a pre-determined way; a theoretical adversary knows what data has just been deleted and will request it. Karp, Fiat, and Luby’s algorithm, on the other hand, chooses the data randomly. The algorithm performed well and served as a foundation for later algorithms that performed optimally – that is, as well as an algorithm can without knowing the future.

In the early 1990s, with the advent of the Human Genome Project, Dick became interested in using combinatorial and probabilistic algorithms to sequence the human genome. Much of the group’s work today focuses on biological problems, with significant efforts led by Eran Halperin in statistical bioinformatics research.

Dick is also a member of the Networking Group and has performed groundbreaking work on data management. In 2000, Dick and other researchers designed an elegant virtual address structure that shares data across several computer systems using hash tables. The content addressable network is a multidimensional space divided into zones, each of which holds some data, has an address, and knows only the addresses of its neighbors. When data is requested, each zone passes the request to a neighbor in the direction of its final destination. The structure organizes itself – so management is not centralized – recovers failures well, and can grow or shrink as needed. It too proved foundational – later work greatly increased its speed. Dick collaborated on the project with Sylvia Ratnasamy, Paul Francis, Mark Handley, and Scott Shenker.

Intellectual Flexibility

In recent years, Dick has begun to look at how theoretical computer science can be applied to fields such economics, social sciences, and biology. He says many natural processes can be described as algorithms – the Internet, for example, which comprises the communication among many people interacting without centralized management. “We can give stochastic algorithmic models of how beliefs and information propagate through a social network,” he said. “We have a tremendous laboratory for that with the World Wide Web.”

This notion of using theory to study the real world, Dick said, “fights against a dictum, which, I think, has had a very toxic effect on computer science … that computer science is a science of the artificial, a science that deals not with naturally occurring entities but with things that we specify.”

“It’s better for science and for the training of computer scientists … to give a lot of priority to explaining information processing in systems that have grown organically,” he said.

The idea of looking at the sciences through a “computational lens” is at the core of the institute to be funded by the Simons Foundation and led by Dick.

His intellectual flexibility has earned Dick numerous accolades over the years – including, notably, the U.S. National Medal of Sciences, the Kyoto Prize, which is described as the Japanese Nobel, and memberships in both the French and U.S. National Academies of Sciences. But for Dick, research is as much a process of failing as it is of succeeding – of trying different approaches to the same problem without any guarantee of success.

Simons’s selection of Dick to lead the center is one of numerous accolades he has received over the years – including, notably, the U.S. National Medal of Sciences, the Kyoto Prize, which is described as the Japanese Nobel, and memberships in both the French and U.S. National Academies of Sciences. But for Dick, research is as much a process of failing as it is of succeeding – of trying different approaches to the same problem without any guarantee of success.

He says, “Enjoy your failures as much as your successes; they will be much more numerous.”