Climbing the staircase in Calvin Lab, home of the Simons Institute for the Theory of Computing, feels like ascending into computer science heaven. Light streams from the gaping skylights, and groups of researchers stand scattered throughout the building’s wide-open spaces. Built in 1963, the lab’s renovation was completed in August, transforming it into a palace of all-glass offices and ultra-modern lounges permeated by the faint sound of science and the even fainter aroma of coffee.
The Simons Institute approaches research in theoretical computer science from an intensely collaborative angle. From the facility itself to a fellowship program and public lectures, the institute encourages communication among researchers, with the Berkeley community and across scientific disciplines. Research at the Simons Institute is posed to answer deep questions with broad implications.
The institute, established July 1 of last year with a $60 million grant from the Simons Foundation, is the first in the world for theoretical computer science research. Such research investigates the deep questions regarding what kinds of problems can be solved or approximated by computers, promising to have applications throughout the sciences and, more importantly, to provide insight into what it means to be “computable.”
The institute pursues answers to these questions through an emphasis on collaboration. Instead of private offices and closed-door meetings, groups of researchers huddle around whiteboards in the expansive naturally lit spaces dotted with candy-colored, soft-touch furniture.
The building itself almost invites researchers to write all over it in their discussions and debates. Writing covers the more than 60 whiteboards inside, the blackboards on the outside walls of the building, even the glass office doors.
“If there’s anything we don’t want written on, we’re going to have to explicitly say it,” said Caroline Allum, events coordinator for the Simons Institute.
Emphasis on collaboration is also reflected in the Simons-Berkeley Research Fellowship. While participating in a mentorship program, the young recipients of the fellowship contribute fully to the scientific work — Alistair Sinclair, associate director of the Simons Institute, called it a “nonhierarchical” system. And the success is already apparent: “We’ve already had a couple papers coming out that have been written by junior and senior people together,” said Sinclair.
The institute also hosts four Open Lectures each semester, in which eminent people “give a fairly gentle, broad-brush” overview of their research, according to Sinclair. The most recent, “How Hard Is It to Find a Good Solution,” gathered people of all backgrounds Nov. 4 to listen to Johan Hastad, a professor at the Royal Institute of Technology in Sweden, discuss research in approximation and complexity theory.
Hastad presented the traveling salesman problem, which sets up a relatively simple scenario: Given a list of cities and the distances between each city, what’s the shortest possible tour that visits each city once before returning to the city from which it started? With 25 cities, the shortest route can be found within one second. But when the number of cities increases, so does the difficulty of finding the best solution — at a rate even faster than exponential.
Computing the best route with 100 cities is “not doable in a lifetime,” Hastad said. And although the problem has been studied since the 1930s, “we don’t really understand what’s going on there.”
The traveling salesman problem illuminates an interesting paradox in theoretical computer science: The problems are often easy to express but difficult to solve. The questions are basic; the thinking, as the dense scrawl on the whiteboards demonstrates, is not.
And those fundamental questions that the Simons Institute aims to answer aren’t limited to the field of computer science. Sinclair described how some problems in fields such as economics, physics, biology and phylogeny are essentially computational.
“Right from the beginning, we always emphasized that ‘theory of computation’ should be taken as broadly as possible, not so much breaking down the boundaries to practice but breaking down the boundaries to other sciences,” he said.
Collaboration at the Simons Institute extends beyond Berkeley, even beyond computer science to the wider scientific community. Theoretical computer science is “a relatively small field — there’s a danger it’ll start to look in on itself, and so I think having an explicitly broad view (is) important,” Sinclair said.
The institute’s research has the potential to shake the very foundations of modern science. Commenting on future research in quantum computing, Sinclair said new discoveries could prompt revision of some assumptions about quantum physics.
Theoretical computer science is deeply interwoven with other scientific fields, and innovation in one often translates to progress in others, according to Sinclair. The Simons Institute uses a fresh computational lens to examine some of the deepest questions in nature, according to the institute’s website.
“The name of the game is that we don’t want to do things the way we’ve always done them,” Hastad said.
