Sparsifying and Derandomizing the Johnson-Lindenstrauss Transform

Jelani Nelson
Massachusetts Institute of Technology
January 31, 2011

The Johnson-Lindenstrauss lemma states that for any n points in Euclidean space and error parameter 0<eps<1/2, there exists an embedding into k = O(eps^{-2} * log n) dimensional Euclidean space so that all pairwise distances are preserved up to a 1+eps factor. This lemma has applications in high-dimensional computational geometry (decreasing dimension makes many algorithms run faster), compressed sensing, and numerical linear algebra.

CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

Santosh Vempala
Georgia Institute of Technology
January 30, 2011
Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming.

Members Seminar: Linear Equations in Primes and Nilpotent Groups

Tamar Ziegler
Technion--Israel Institute of Technology
January 30, 2011
A classical theorem of Dirichlet establishes the existence of infinitely many primes in arithmetic progressions, so long as there are no local obstructions. In 2006 Green and Tao set up a program for proving a vast generalization of this theorem. They conjectured a relation between the existence of linear patterns in primes and dynamics on nilmanifolds. In recent joint work with Green and Tao we completed the final step of this program.

Periodic Bounce Orbits of Prescribed Energy

Peter Albers
Purdue University
January 26, 2011


Periodic bounce orbits are generalizations of billiard trajectories in the presence of a potential. Using an approximation technique by Benci-Giannoni we prove existence of periodic bounce orbits of prescribed energy. At the end of the talk I will sketch very recent work in which we allow much more general Lagrangian systems including magnetic and Finsler billiards.

This is joint work with Marco Mazzucchelli.

Learning with Boolean Threshold Functions, a Statistical Physics Perspective

Rémi Monasson
Ecole Normale Superieure; Simons Center for Systems Biology, IAS
January 25, 2011

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered systems to characterize BTF in a quantitative way [1], with an emphasis on computational and geometrical aspects. These techniques will be illustrated on two particular cases: the celebrated perceptron (Linear Threshold Function) [2], and the more realistic tempotron model of a neuron [3,4].

The Cartan Geometry of the Rotating Kepler Problem

Otto van Koert
Seoul National University
January 21, 2011


In this talk we shall discuss the Cartan geometry of the rotating Kepler problem. The rotating Kepler problem appears as the limit of the restricted planar three-body body when one of the masses goes to zero. As such, this problem plays the role of a simple approximation. We shall discuss the Cartan curvature and some of its relations with indices in the three-body problem. This is joint work with Kai Cieliebak and Urs Frauenfelder.