Polynomial-time tensor decompositions via sum-of-squares

Tengyu Ma
Princeton University
March 21, 2016
Tensor decompositions have been the key algorithmic components in provable learning of a wide range of hidden variable models such as topic models, Gaussian mixture models, independent component analysis, dictionary learning. Despite its success, one of the challenges in this area is to decompose over-complete 3rd-order tensors robustly.

The Resolution proof system

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
March 22, 2016
The Resolution proof system is perhaps the simplest and most universally used in verification system and automated theorem proving. It was introduced by Davis and Putnam in 1960. The study of its efficiency, both in terms of proof length of natural tautologies and in terms of the complexity of finding short proofs has lead over the decades to a rich understanding which is nonetheless incomplete.

Slowly converging pseudo-Anosovs

Mark Bell
University of Illinois, Urbana-Champaign
March 22, 2016
A classical property of pseudo-Anosov mapping classes is that they act on the space of projective measured laminations with north-south dynamics. This means that under iteration of such a mapping class, laminations converge exponentially quickly towards its stable lamination. We will discuss a new construction (joint with Saul Schleimer) of pseudo-Anosovs where this exponential convergence has base arbitrarily close to one and so is arbitrarily slow.

Low-lying, fundamental, reciprocal geodesics

Alex Kontorovich
Rutgers University; Member, School of Mathematics
March 24, 2016
Markoff numbers give rise to extremely low-lying reciprocal geodesics on the modular surface, but it is unknown whether infinitely many of these are fundamental, that is, the corresponding binary quadratic form has fundamental discriminant. In joint work with Jean Bourgain, we unconditionally produce infinitely many low-lying (though not "extremely" so), reciprocal geodesics on the modular surface, settling a question of Einsiedler-Lindenstrauss-Michel-Venkatesh.

A local central limit theorem for triangles in a random graph

Swastik Kopparty
March 28, 2016
What is the distribution of the number of triangles in the random graph $G(n, 1/2)$? It was known for a long time that this distribution obeys a central limit theorem: from the point of view of large intervals (~ standard-deviation length), the distribution looks like a Gaussian random variable. We show that it even obeys a LOCAL central limit theorem: the distribution is pointwise close to a suitable discrete Gaussian random variable. Joint work with Justin Gilmer.

Apollonian packings and the quintessential thin group

Elena Fuchs
March 28, 2016

Schedule: https://sites.google.com/site/thingroups/schedule

In this talk we introduce the Apollonian group, sometimes coined the “quintessential”
thin group, which is the underlying symmetry group of Apollonian circle packings. We
review some of the exciting results that have been proven with respect to number-theoretic
aspects of these packings, and indicate where super-approximation plays a role.

Super-approximation I

Alireza Salehi Golsefidy
March 28, 2016
Abstract: Let Γ be a finitely generated subgroup of a compact group G.
1. I will recall what it means to say the action of Γ on G by left translation has spectral
gap, and mention some examples and applications, e.g. Banach-Ruziewicz problem, explicit
construction of expanders.
2. I will give the precise formulation of super-approximation conjecture and present the
best known results.
3. I will mention some new applications, e.g. orbit equivalence rigidity, variation of
Galois representations.

Super-approximation II

Alireza Salehi Golsefidy
March 28, 2016
I will explain the Bourgain-Gamburd method of proving spectral gap. The spirit
of this method is behind all the recent results on this subject. Very roughly it says in order
to prove spectral gap it is enough to show that a “generic” subset with positive “box dimension”
generates a “large” subgroup in a controlled number of steps (bounded generation).
The vague terms will be explained, and we will see their connections with understanding the
structure of a “generic” approximate subgroup with positive “box dimension”.