By Kristin Kane
In 1943, at the height of the war, Alan Turing left his office at Bletchley Park and set off across the Atlantic for the United States. During his stay, he spent two months at Bell Labs talking to Claude Shannon, now regarded as the father of the field of Information Theory. What did the two men talk about during those long afternoons on the Hudson? What insights may have justified Turing’s trip through U-Boat-infested waters?
The details of the conversations at Bell Labs that spring in 1943 have been lost to history. But the dialogue between the disciplines they created – Information Theory (the mathematical underpinning of communication engineering) and Computer Science – is center stage this semester at the Simons Institute.
Alongside its goal of fostering research on core questions in the theory of computing, a key aim of the Simons Institute is to seed new areas of research at the interface of theoretical computer science and outside fields with core problems that are computational in nature. An example of fruitful cross-fertilization was the program on Quantum Hamiltonian Complexity that took place at the Institute in Spring 2014. This program, which explored connections at the intersection of computational complexity and condensed-matter physics, had its genesis at a planning workshop held in February 2013.
“We had been exploring the connections from each end,” remembers Umesh Vazirani, one of the organizers of the program, and a faculty member in Computer Science at UC Berkeley. “And it’s of course hard to do that, because there’s such a big language barrier between the fields. It was clear to us that it couldn’t be a standard workshop, because we wanted something special from it. And so we had to throw the usual way of organizing things out the window, and start from new principles.”
From the beginning, the organizers of the Quantum Hamiltonian Complexity program wanted to think innovatively about how to structure interactions to foster deep insights and the creation of a common language. In that initial planning workshop, they decided that the questions and conversation arising naturally during a talk would be given free rein to play out, even if it meant adjusting the schedule in real time.
Taking this successful workshop as a “proof-of-concept”, the organizers extended the principle to the semester-long program. Here too, pride of place was given to the insights that can emerge through conversation. Seminar presenters were told that their role was to put forth one idea, and then let everyone else speak. The next time there was an awkward silence, the presenter would have a chance to share another idea.
“There were two thoughts,” says Vazirani. “One was that we wanted to develop this common language; that was very much a goal. But the second thing was: You have all these smart people around. You don’t want them just to listen. It’s that you have experts who know stuff – and they know interesting stuff. And suddenly you understand so much more about this thing than any of you would have by yourself. It’s a wasted opportunity if you don’t do that.”
Sometimes interdisciplinary connections emerge not only within an individual program, but across the boundaries between programs. The Fall 2014 program on Algorithms and Complexity in Algebraic Geometry brought together a combination of pure and applied mathematicians with complexity theorists. This particular coalition overlapped in interesting ways with the group of applied mathematicians and computer scientists in the concurrent program on Algorithmic Spectral Graph theory. There were a number of shared talks, and many of the participants attended workshops from both programs. With so many activities of interest, and new collaborations arising unexpectedly over daily tea, it was a lively – and very busy – semester. “It was sort of overkill,” remarks Algebraic Geometry organizer Bernd Sturmfels, a professor of Mathematics at UC Berkeley. “But a happy overkill, I would say.”
The Institute’s interdisciplinary programs fall at various different points in the development pipeline – from the established collaboration between statisticians and computer scientists in the Fall 2013 program on Big Data, to much more preliminary explorations. The Evolutionary Biology program in Spring 2014 brought together an alliance of biologists, physicists, statisticians and probabilists – communities with a successful history of cross-disciplinary collaboration on topics in evolutionary biology – with a group of theoretical computer scientists who had been exploring models and theories of evolution from a computational vantage point. The overarching objective was to begin a conversation between these two communities that had not previously worked together: to create a shared language, and to explore possibilities for collaboration.
From the first day of the program, however, it was clear that the bridge would not be fully built in a day, or even in a semester. Significant differences in paradigm between the two communities created unique challenges for this ambitious program.
“I think the culture is different,” reflects Shishi Luo, a Research Fellow in the program, and now a postdoc at UC Berkeley in Computer Science and Statistics. “The more applied you get, the more the aim of the research is to get the answer to a question; it doesn’t matter how pretty your method is. Whereas I think theoretical computer scientists are also interested in the aesthetics of the method, coming up with a nice proof. And so they would want to make assumptions that would make it easier for them to do that work.”
Differing research assumptions, compounded by different tools and vocabulary, led to lively debate and some radical new ideas, as exemplified in Research Fellow Adi Livnat’s Vignette in last month’s newsletter, which argues that many of the mutations that drive evolution may be non-accidental results of biological processes.
In the course of the program, the two groups learned a lot about each other’s approaches and core questions. And pathways to collaboration were opened, especially among the Research Fellows, who as young scholars are still developing their research programs. The conversations that began during the Simons Institute program on Evolutionary Biology were widely acknowledged to be timely and intriguing. As for where they will lead, only time will tell.
Letter from the Director
From the Inside: Information Theory
Research Vignette: Faster Algorithms for Linear Programming
Research Vignette: Semialgebraic Geometry of Ranks
Program Preview: Cryptography