School of Mathematics

CSDM - The Completeness of the Permanent

Amir Yehudayoff
Institute for Advanced Study
September 22, 2009

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We will describe the ideas behind the proof of this completeness of the permanent.

CSDM - Twice-Ramanujan Sparsifiers

Nikhil Srivastava
Yake University
September 21, 2009

We prove that every graph has a spectral sparsifier with a number of edges linear in its
number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our
sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs.
In particular, we prove that for every d > 1 and every undirected, weighted graph G =
(V,E,w) on n vertices, there exists a weighted graph H = (V, F, ~w) with at most dn edges
such that for every x ∈ ℜV ,


Science and Technology in the Developing World: The Institute's Role

Phillip A. Griffiths
Institute for Advanced Study
May 1, 2009

For the past decade, the Institute’s Science Initiative Group (SIG) has worked with the World Bank and other partners to strengthen science in developing nations. In this talk, Phillip Griffiths, who helped create SIG when he was Director of the Institute from 1991 to 2003, will address the context for and evolution of SIG’s programs, with emphasis on the new Carnegie–IAS Regional Initiative in Science and Education (RISE), which prepares Ph.D.-level scientists and engineers in sub-Saharan Africa through university-based research and training networks.

Search for Randomness

Jean Bourgain
Institute for Advanced Study
March 25, 2009

Although the concept of randomness is ubiquitous, it turns out to be difficult to generate a truly random sequence of events. The need for “pseudorandomness” in various parts of modern science, ranging from numerical simulation to cryptography, has challenged our limited understanding of this issue and our mathematical resources. In this talk, Professor Jean Bourgain explores some of the problems of pseudorandomness and tools to address them.