Monday, October 20th, 2014

Newsletter – Fall 2014

Profile of Luca Trevisan, the Simons Institute's Incoming Senior Scientist


The Simons Institute is pleased to announce the appointment of Luca Trevisan as our first permanent Senior Scientist. Luca rejoined UC Berkeley this fall, with joint appointments at the Simons Institute and Department of Electrical Engineering and Computer Sciences, and the Department of Mathematics. He comes to us most recently from Stanford University, where he was a Professor of Computer Science. He has also held posts at Columbia University, MIT and DIMACS, and earned his Ph.D. from the Sapienza University of Rome, under Pierluigi Crescenzi.

This video introduction features Luca in conversation with Interim Senior Scientist, Christos Papdimitriou.

Letter from the Director

Dear friends of the Simons Institute,

As I write this article, Calvin Lab, the home of the Simons Institute, is abuzz with a hundred visiting scientists from around the world who have gathered to participate in our Fall 2014 programs on Algorithmic Spectral Graph Theory and Algorithms and Complexity in Algebraic Geometry. Read More »


From the Inside

Our “From the Inside” series offers profiles of programs currently underway at the Institute.

Spectral logoAlgorithmic Spectral Graph Theory

By James R. Lee

At its most basic, spectral graph theory exploits the eigenvalues and eigenvectors of a graph to study it from a global perspective. While a myopic examination of a few vertices and edges (friends and friendships) in a social network might leave one in the dark about its community structure, even a single eigenvector can carry detailed information about large-scale phenomena. Read More »

Algebraic Geometry logoAlgorithms and Complexity in Algebraic Geometry

By JM Landsberg

Nearly all scientists use linear algebra and recognize its importance. The utility of algebraic computation beyond linear algebra is just beginning to be recognized and exploited. Algebraic geometry studies the zero sets of collections of polynomials, both quantitatively and qualitatively. It is one of the oldest areas of mathematics. In the second half of the last century, algebraic geometers developed abstract language that enabled them to solve questions that had been open for hundreds of years. An unfortunate byproduct of this language was that, despite its utility, the subject became inaccessible to researchers outside the field. Read More »


Research Vignettes

Our new Research Vignette series showcases interesting research results that emerged during the most recent semester’s programs. The first article, by Adi Livnat, is an example of the exciting and provocative proposals that come out of our programs, and should give rise to lively debate. The second, by Thomas Vidick, is a case study in the kind of interdisciplinary collaboration fostered by the Institute.

On Sex, Math, and the Origin of Life

By Adi Livnat

One of the most fascinating kinds of mathematical work is to create a new mathematical framework where none has existed before. Two cases in point are Turing’s 1936 paper and von Neumann’s and Morgenstern's Theory of Games and Economic Behavior. In the Simons program on Evolutionary Biology and the Theory of Computing, an opportunity was presented for creating a new mathematical framework for evolution based on new ideas and empirical knowledge, with implications for wide-ranging topics—from sex to genetic disease to the origin of life. Read More »

Quantum PCP Conjectures

By Thomas Vidick

The macroscopic properties of materials arise from the physical interactions between their constituent particles. For example, the use of the Pauli exclusion principle explains how the conductivity properties of a material follow from the energy band structure of its atoms. Techniques for performing the extrapolation from microscopic laws to macroscopic predictions form the basis of statistical mechanics. The implied statistical averaging, however, is insufficient to predict certain properties, such as superconductivity, for which subtle quantum mechanical effects need to be taken into account. Read More »


Upcoming Programs

Information Theory, Jan. 13 – May 15, 2015

Information Theory logoThis program will bring together experts in information theory and theoretical CS to explore the application of information theoretic techniques in complexity theory and combinatorics, the theory and applications of coding theory, and connections between information theory, machine learning and big data. Read More »

Cryptography, May 18 – Aug. 14, 2015

Cryptography logoAs organizations and individuals are increasingly outsourcing storage and computation to large third-party systems, the need to simultaneously guarantee privacy, availability of data and correctness of computations is more crucial than ever. This program focuses on new developments in cryptography that address these issues, including homomorphic encryption, program obfuscation and verifiable outsourcing. Read More »