Simons Institute for the Theory of Computing Opens in Berkeley

The Simons Institute for the Theory of Computing, housed on the campus of the University of California, Berkeley, held an opening celebration on March 31, 2014. The institute, established in 2012 by a grant from the Simons Foundation, brings together leading researchers to explore both the theoretical underpinnings of computer science and its potential to shed light on a wide range of natural phenomena that other scientific disciplines study.

The institute’s activities center on semester-long programs, which attract large groups of visiting scholars; there are currently more than 100 long-term visitors attending the Spring 2014 programs. As part of the celebration, three participants in recent and ongoing programs made presentations. The talks were held in several different parts of the institute’s building, to highlight that the facility, formerly a chemistry wet lab, has been repurposed to create extensive open areas that facilitate collaboration. These interaction spaces “are bubbling with creative energy,” said Richard Karp, the institute’s director. He thanked the renovation team for creating “a light-filled space devoted to gatherings at whiteboards, the drinking of coffee, and the making of theorems.”

Iain Mathieson of Harvard University spoke about the institute’s current program on evolutionary biology and the theory of computing. Increasingly, he said, problems in evolutionary biology can be viewed through the lens of computer science. Mathieson’s own work, for instance, involves employing computer algorithms to identify segments of different people’s genomes that were inherited from common ancestors, and then using the statistics of those segments to make more accurate estimates of the timing of major events in human prehistory, such as the migrations from Africa about 100,000 years ago. Workshop participants, Mathieson said, have also been discussing how to use techniques from machine learning to understand which of the variations across different people’s genomes have resulted from adaptation to different environments, and which are due to random chance.

Dorit Aharonov of the Hebrew University of Jerusalem described the institute’s current semester-long program on quantum Hamiltonian complexity, a novel area of research that combines insights from theoretical computer science and quantum physics. The program has brought together physicists and computer scientists to tackle fundamental physics problems, such as the question of how to test the theory of quantum mechanics even though simulations of even small quantum systems are not computationally feasible. A computer science approach called ‘interactive proofs’ — which gives a way to test a purported proof or computation by throwing random questions at the prover — offers a potential way forward, Aharonov noted. “Insights from computer science are shedding light on physics questions that seem completely unrelated,” she said. “The diversity of things we’re touching on in the program is really exciting.”

Michael Jordan of the University of California, Berkeley spoke about the Fall 2013 program on the theoretical foundations of big data analysis. Big data, Jordan noted, are now emerging from nearly all areas of science and commerce. Figuring out how to make effective inferences from these data, he said, will require a marriage of statistics, which deals in risk and uncertainty, and computer science, which deals in algorithms and resources, such as time and space. The program’s goal was to develop a framework for understanding the core conceptual challenges of big data, “so we can make good decisions about data regularly and repeatedly and fast,” Jordan said. The program included researchers in theoretical computer science, statistics, optimization theory and other areas of mathematics. “It’s the first time all of those areas have come together in one collection of people thinking together.”

The interdisciplinary nature of these three programs is far from accidental: Such collaborations are at the core of the institute’s mission, Karp explained at the opening ceremony. “The institute is based on a broad conception of the theory of computing, not only as a fundamental mathematical discipline, but as a foundation for revolutionary developments that are influencing the fabric of society and the methodology of every branch of science and engineering.”