Current and Upcoming Programs

By Christos Papadimitriou

The core of the Institute’s scientific activity consists of semester-long scientific programs, two per semester. Each program is put together by a committee of four to six Organizers who typically commit to spending the whole semester at the Institute, and brings to the Institute many other senior visitors, as well as around eight Simons Fellows – postdocs and early-career researchers – as well as graduate students. Each program includes several week-long workshops, which attract a larger scientific community; programs typically start with a “boot camp,” with intense introductory lectures designed to bring all participants onto the same page. Programs are selected on the basis of detailed proposals evaluated semiannually by the Institute’s Scientific Advisory Board. The Institute commits to programs at least two years in advance, and always welcomes strong proposals for important subareas of the theory of computing, or its interface with other scientific fields.

The Institute opened its doors in August of 2013. By now we have behind us the two hugely successful programs of Fall 2013 ("Theoretical Foundations of Big Data Analysis," and "Real Analysis in Computer Science") and we are approaching the end of two exciting, and so far also extremely successful, programs exploring the interface of the theory of computation with two weighty realms of science: quantum physics, and the theory of evolution.

In the century-and-a-half since the publication of The Origin of Species, evolution has grown into a mature field of scientific inquiry informed by biology, genetics, statistics, and mathematics; in addition, several researchers in the theory of computing have recently joined in, offering models and explanations for aspects of evolution inspired by algorithms, complexity and machine learning. With the recent avalanche of genomic data, the theory of evolution has entered a phase of rapid expansion and potentially deep transformation. The program on "Evolutionary Biology and the Theory of Computing" now running at the Institute is bringing together researchers from all these disciplines, including the theory of computing, to exchange their latest ideas and collaborate in advancing our understanding of the area’s fundamental problems at this critical juncture. The program is organized by UC Berkeley’s Yun Song, assisted by Andrew Clark (Cornell), Rick Durrett (Duke), Charles Langley (UC Davis), Christos Papadimitriou (UC Berkeley), and Les Valiant (Harvard). We have had two workshops so far, one on the computer-intensive statistical and probabilistic methods currently used to understand large-scale population genomics data, and the other on Computational Theories of Evolution, in which computer scientists presented their point of view and results for the scrutiny of others, while many evolutionary biology and genetics researchers presented ideas and results evocative of computation. The final workshop, on new directions in probabilistic models of evolution, takes place the week of April 28.

Quantum computing, the vision that one day computational devices able to exploit quantum-mechanical phenomena will outperform classical computers, was first conceived by Richard Feynman in the 1980s, and was made mathematically concrete by computer scientists a decade later. It is a very active field, involving computer scientists interacting with theoretical and experimental physicists to realize this dream and, in the meantime, pursue its mathematical consequences. The Institute’s program on "Quantum Hamiltonian Complexity" focuses on one particular aspect of this growing field, inspired by a connection between the theories of complexity and condensed matter physics: the local Hamiltonian in a quantum system has many mathematical correspondences with the quantum analogue of the satisfiability problem in complexity theory. One key question addressed by this program is whether quantum systems with a substantial eigenvalue gap in their Hamiltonian have a simpler structure captured by an “area law” – the property that the amount of entanglement across a surface is proportional to the area of the surface, instead of the surrounding volume. Another question is whether high temperature moderates the exponential complexity of representing a quantum system, and this turns out to have a complexity analogue that is already known, but difficult to prove (the PCP Theorem). Finally, a third question examines whether, in the absence of an implemented quantum computer, the outcomes of scientific experiments in quantum mechanics can even be predicted – that is to say, whether the scientific method is possible in this context. This, again, turns out to relate to the “interactive protocol” formulation of PSPACE in complexity theory. The program organizers are Umesh Vazirani of UC Berkeley, Dorit Aharonov of the Hebrew University, Jerusalem, Matt Hastings of Microsoft Research, and Frank Verstraete of the University of Vienna. Two workshops so far have explored quantum games and protocols on the one hand, and the connection to condensed matter physics on the other. A third workshop, which took place during the week of April 21, focused on tensor networks and simulations.

This coming fall, the Institute will host two exciting semester-long programs, one on "Algorithmic Spectral Graph Theory," and the other on "Algorithms and Complexity in Algebraic Geometry." “Spectral” refers to techniques that involve the eigenvectors and eigenvalues of matrices and other operators, concepts that have long been central in functional analysis and numerical computation. It had been known for decades that these same mathematical tools can be applied usefully to graphs by considering the adjacency matrix of the graph, or a variant called the Laplacian. During the last decade, work by theoretical computer scientists and others spearheaded a revolution in this area: computing the spectrum of a graph can now be done in near-linear time through spectacular algorithmic innovation, while the resulting techniques have precipitated breakthroughs in fundamental problems such as network flow. In the process, important mathematical insights such as Cheeger’s inequality have been generalized. The goal of the semester at the Simons Institute is to capture this excitement and launch the area forward by bringing together world-renowned algorithm designers, complexity theorists, mathematicians and practitioners. Three workshops will explore current and new aspects of this field: one workshop will fathom the connection between spectral methods and the approximability of intractable optimization problems, including the important Unique Games Conjecture, through semidefinite programming; another workshop will focus on fast algorithms based on spectral methods, while yet another will examine how these deep ideas and results can be transferred all the way to practical computation. The semester’s organizers include well-known leaders of all aspects of this area: James R. Lee (U. Washington), Prasad Raghavendra (UC Berkeley), Ravi Kannan (Microsoft Research), Jitendra Malik (UC Berkeley), Gary Miller (CMU), and Luca Trevisan (Stanford).

Algebraic Geometry, the study of the geometry of the roots of multivariate polynomials, is one of the most prestigious and deep areas of mathematics, and an indispensable framework for the study of many diverse fields, from number theory to mathematical physics – and, as it turns out, the theory of computing. The connections to computation are many, ranging from the matrix multiplication problem and algebraic complexity to the geometric rendering of the P vs NP question, and includes many concretely algorithmic problems that are central to the field. The goal of the program on Algebraic Geometry next fall is to bring together theoretical computer scientists and algebraic geometers so that they can develop a common language and culture and collaborate toward the discovery of powerful new mathematical tools and new vistas of applications. The organizers include accomplished algebraic geometers with a track record at the interface with computation (Joseph Landsberg and Bernd Sturmfels) and complexity theorists who have pioneered the algebraic-geometric connection (Peter Bürgisser and Ketan Mulmuley). There will be a workshop on the geometric approach to complexity, one on solving systems of polynomial equations, and one on tensor algebra and tensor rank.

Related Articles:

Letter from the Director
The Renovation of Calvin Lab: A Photo Essay
Program Retrospective: Theoretical Foundations of Big Data Analysis
Program Retrospective: Real Analysis in Computer Science
Life at the Simons Institute: A Fellow's Perspective
Official Opening of the Simons Institute