Recently Added

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.

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.

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.

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.

Ramanujan Graphs and Siran Graphs, Applications to Classical and Quantum Coding Theory

Jean-Pierre Tillich
INRIA, France
March 16, 2012

We explain in this talk how Ramanujan graphs can be used to devise optimal cycle codes and review how other graph families related to a construction proposed by Margulis yield interesting families of quantum codes with logarithmic minimum distance. We finish the talk by providing another simple graph theoretic construction with improved minimum distance which grows proportionally to the square root of the quantum code length. (This is joint work with Gilles Zemor.)

Applications of FT-Mollification II

Jelani Nelson
Institute for Advanced Study
March 13, 2012

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. This is a continuation of my talk from last week, and I will continue to describe this approach and show how it can be used to show that bounded independence fools polynomial threshold functions over various distributions (Gaussian, Bernoulli, and p-stable). I may also touch on other applications in approximation theory and learning theory.

Computational Aspects in the Braid Group and Applications to Cryptography

Mina Teicher
Bar-Ilan University; Member, School of Mathematics
March 12, 2012

The braid group on n strands may be viewed as an infinite analog of the symmetric group on n elements with additional topological phenomena. It appears in several areas of mathematics, physics and computer sciences, including knot theory, algebraic geometry, quantum mechanics, quantum computing and cryptography.