Berkeley Tops Competition for Simons Institute in Theoretical CS

June 23, 2012

Richard Karp, founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley, takes an expansive view of what already seems to be a uniquely favored institute. To be situated in the heart of the Berkeley campus, with a $60 million ten-year award from the Simons Foundation, the institute was established, Karp says, to serve the worldwide community in theoretical science and to be a magnet for top scientists in the field.

Early in May, shortly after learning that Berkeley had won the award, Karp gave SIAM News a brief tour of the landscape in which the new institute's interests lie. Many in the SIAM community, with its own varied topography, will recognize intersections and connections with their own work, and with themes of many SIAM conferences and publications.

Computational complexity, cryptography, the logic of programs, and other areas familiar to those who study the mathematical foundations of computer science will be central to activity at the Simons Institute. But by looking from a theoretical point of view at computational processes arising in a wide variety of systems---in nature, in humanly engineered edifices, on the web---the institute's leaders intend to broaden the scope of the field.

At many levels, Karp says, "nature seems to be computing in some sense." The immune system is, figuratively, executing an algorithm, he points out; protein folding can be seen as a computational process, as can evolution.

Lest he appear to be overemphasizing biology (his own recent interests include algorithmic methods in genomics), Karp cites statistical physics, with its very close ties to mathematics, as a rich area for exploration by institute scientists. Statistical physics, he points out, draws on mathematics very similar to Markov processes in such problems as finding the equilibrium configuration of a set of magnetic spins. Markov chain Monte Carlo can be used to determine the distribution of states in an Ising model in statistical physics.

Economics comes into play, in the form of, say, auction theory. It turns out, Karp says, that algorithmic game theory can be seen in the context of computational complexity, a major theme in theoretical computer science. Here he cites a recent result by Berkeley computer scientist Christos Papadimitriou (with C. Daskalakis and P.W. Goldberg) that computing a Nash equilibrium is computationally intractable.

Consistent with Karp's descriptions is the list released in a statement by UC Berkeley of the four initial big questions to be considered at the institute: "how the diversity of life on Earth evolved in only 4 billion years"; regulatory mechanisms that govern the immune response or the genesis of cancer; database privacy; and, perhaps with the least obvious connection to theoretical computer science, improved models of climate change.

Institute scientists will not work exclusively on problems in other sciences, Karp wants to make clear. Intrinsic problems of computer science, such as P vs. NP, will be pursued, as will work in discrete analysis.

Discrete analysis, in fact, is the topic of one of the first semester-long programs the institute will run, in the fall of 2013; big data is the other. And two programs per semester will be the format for the fully operational Simons Institute, which Karp expects to draw about sixty scientists to the campus at any one time. Included in that total are four permanent faculty: Karp, as director; Alistair Sinclair, also a computer scientist at Berkeley, as associate director; and two other senior scientists with the experience and flexibility to serve as mentors as the scientific focus changes from semester to semester (filling those two positions will be a priority during the institute's first two years). Sixty scientists are expected to participate in programs each semester, including sixteen postdocs.

Among the main assets of the institute, Karp mentions interactions with other Berkeley people, groups, and centers: CITRIS, the Center for Information Technology Research in the Interest of Society, of which Jim Demmel is former chief scientist; Lawrence Berkeley National Lab; MSRI, the Mathematical Sciences Research Institute; the International Computer Science Institute (where Karp, until he took on the institute directorship, spent half of his time as head of the algorithms group); and the Miller Institute for Basic Research in Science. Not least is the university itself, which has provided both cooperation and financial support, including slots for several graduate students and, perhaps most significantly, the centrally located building, former home of chemistry labs, that is now being renovated for the institute.

Beyond, but not too far beyond, the university, lies another important resource: Silicon Valley IT firms, including Google, the institute's first founding industrial partner. In such areas as big data, search, the science of advertising, and auctions, Karp hopes that the institute will be able to draw on the expertise of the leading researchers at some of those firms. In the end, though, the Simons Institute is international. Whether through joint postdocs or participation in programs, Karp mentions connections already forged with Tsinghua University, with Microsoft India, and with others around the world. And, of course, institute leaders have on-
going ties to SIAM--"a very natural community to interact with us."---GRC

• See more news from this issue