Sparsity Lower Bounds for Dimensionality Reducing Maps

Jelani Nelson
Member, School of Mathematics
January 22, 2013

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show:
(1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up to a log(1/eps) factor.
(2) RIP_2 matrices preserving k-space vectors in R^n with the optimal number of rows must be dense as long as k < n / polylog(n).

Hamiltonian Evolution Equations -- Where They Come From, What They Are Good For

Juerg Frohlich
ETH Zurich; Member, School of Mathematics
January 22, 2013

Several examples of Hamiltonian evolution equations for systems with infinitely many degrees of freedom are presented. It is sketched how these equations can be derived from some underlying quantum dynamics ("mean-field limit") and what kind of physics they describe.

Sphere Packing Bounds Via Spherical Codes

Henry Cohn
Microsoft Research New England/MIT
January 22, 2013

We develop a simple geometric variant of the Kabatiansky-Levenshtein approach to proving sphere packing density bounds. This variant gives a small improvement to the best bounds known in Euclidean space (from 1978) and an exponential improvement in hyperbolic space. Furthermore, we show how to achieve the same results via the Cohn-Elkies linear programming bounds, and we formulate a few problems in harmonic analysis that could lead to even better bounds. This is joint work with Yufei Zhao.

Abelian varieties with maximal Galois action on their torsion points

David Zywina
January 24, 2013

Associated to an abelian variety A/K is a Galois representation which describes the action of the absolute Galois group of K on the torsion points of A. In this talk, we shall describe how large the image of this representation can be (in terms of a number field K and the dimension of A). We achieve this by considering abelian varieties in families and then using a special variant of Hilbert's irreducibility theorem. Some results of Serre on the mod ell Galois image will also be reviewed. (This is joint work with David Zureick-Brown)