Vertex Sparsification: An Introduction, Connections and Applications

Ankur Moitra
Massachusetts Institute of Technology; Institute for Advanced Study
November 8, 2011

The notion of exactly (or approximately) representing certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are given a graph $G = (V, E)$ and a set of terminals $K \subset V$ and our goal is to find one single graph $H = (K, E_H)$ on just the terminal set so that $H$ approximately preserves the minimum cut between every bi-partition of the terminals.

Around the Davenport-Heilbronn Function

Enrico Bombieri
Institute for Advanced Study
November 10, 2011

The Davenport-Heilbronn function (introduced by Titchmarsh) is a linear combination of the two L-functions with a complex character mod 5, with a functional equation of L-function type but for which the analogue of the Riemann hypothesis fails. In this lecture, we study the Moebius inversion for functions of this type and show how its behavior is related to the distribution of zeros in the half-plane of absolute convergence. Work in collaboration with Amit Ghosh.

Orientability and Open Gromov-Witten Invariants

Penka Georgieva
Princeton University
November 11, 2011

I will first discuss the orientability of the moduli spaces of J-holomorphic maps with Lagrangian boundary conditions. It is known that these spaces are not always orientable and I will explain what the obstruction depends on. Then, in the presence of an anti-symplectic involution on the target, I will give a construction of open Gromov-Witten disk invariants. This is a generalization to higher dimensions of the works of Cho and Solomon, and is related to the invariants defined by Welschinger

 

Education and Equality

Danielle Allen, UPS Foundation Professor
Institute for Advanced Study
November 16, 2011

Current educational policy discussions frequently invoke “equality” as the reigning ideal. But how clear a view do we have of what we mean by this? What exactly are we trying to achieve? In this lecture, Danielle Allen, UPS Foundation Professor in the School of Social Science, revisits the question of how to understand the ideal of equality in the context of educational policy.

An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-Degree Graphs

Siavosh Benabbas
Institute for Advanced Study
November 21, 2011
In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closest even integer) coordinates. How big can the set of chosen strings be? Erdos conjectured that the answer is small (in a precise sense) and put a $250 prize for a solution. In 1987 Frankl and Rodl proved a strong form of this conjecture showing that such a set has to be exponentially smaller than the set of all strings of length n.

The Global Water Crisis and the Coming Battle for the Right to Water

Maude Barlow
Chair of the Council of Canadians and Chair of Food and Water Watch
November 30, 2011

The world is running out of available water supplies, and the potential for conflict will be severe. In this lecture, Maude Barlow, Chair of the Council of Canadians and Chair of Food and Water Watch, sets out the nature and cause of the crisis and offers a three-part solution to achieve a water-secure world.