## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, September 29, 2011, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Sebastian Stich

## The Johnson-Lindenstrauss Lemma

The Johnson-Lindenstrauss Lemma asserts that a set of n points in any Euclidean space can be mapped to an Euclidean space of dimension k=O(\epsilon^{-2} \log n) so that all distances are preserved up to a multiplicative factor between (1-\epsilon) and (1+\epsilon). Known proofs obtain such a mapping as a linear map R^n -> R^k with a suitable random matrix U. The structure of U can be surprisingly simple, e.g. independent Gaussian entries (Indyk and Motwani, 1998), independent -1,1 entries (Achlioptas 2001) and even sparse (Ailon and Chazelle 2006, Matousek 2007).

We give an overview of these results and present an elementary proof of the result obtained by Indyk and Motwani.

Information for students and suggested topics for student talks