The Quasi-Polynomial Freiman-Ruzsa Theorem of Sanders

Shachar Lovett
Institute for Advanced Study
March 20, 2012

The polynomial Freiman-Ruzsa conjecture is one of the important open problems in additive combinatorics. In computer science, it already has several diverse applications: explicit constructions of two-source extractors; improved bounds for the log rank conjecture in communication complexity; and lower bounds for locally decodable codes based on matching vectors codes. Recently, Tom Sanders proved a quasi-polynomial version of this conjecture. I will describe the polynomial Freiman-Ruzsa conjecture, its applications and the proof of Sanders theorem.

Nodal Lines of Maass Forms and Critical Percolation

Peter Sarnak
Institute for Advanced Study
March 20, 2012

We describe some results concerning the number of connected components of nodal lines of high frequency Maass forms on the modular surface. Based on heuristics connecting these to a critical percolation model, Bogomolny and Schmit have conjectured, and numerics confirm, that this number follows an asymptotic law. While proving this appears to be very difficult, some approximations to it can be proved by developing number theoretic and analytic methods. The work report on is joint with A. Ghosh and A. Reznikov.

Graph Convergence, Parameter Testing and Group Actions

Miklos Abert
Alfred Renyi Institute of Mathematics, Budapest
March 20, 2012

I will talk about two natural notions of convergence for sequences of graphs of bounded degree and their connection to groups and group actions. The first is Benjamini-Schramm convergence, which is strongly related to parameter testing. The second is local-global convergence, introduced by Hatami, Lovasz and Szegedy. I will discuss recent results on roots of graph polynomials (including the chromatic polynomial and Tutte polynomials), the combinatorics of expander graphings, and the geometry of locally symmetric spaces.

Arnold Diffusion via Normally Hyperbolic Invariant Cylinders and Mather Variational Method, Part II

Ke Zhang
Institute for Advanced Study
March 21, 2012

In 1964 Arnold constructed an example of instabilities for nearly integrable systems and conjectured that generically this phenomenon takes place.
There has been big progress attacking this conjecture in the past decade. Jointly with Ke Zhang we present a new approach to this problem. It is based on a construction of crumpled and flower Normally Hyperbolic Invariant Cylinders. Once existence of these cylinders is shown to construct diffusion we apply Mather variational mechanism. A part of the project is also joint with P. Bernard.

Higher-Order Cheeger Inequalities

Luca Trevisan
Stanford University
March 27, 2012

A basic fact of algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse (non-expanding) cut if and only if there are at least two eigenvalues that are close to zero.