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.

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.

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.