# Embeddings of Discrete Groups and the Speed of Random Walks

 COMPUTER SCIENCE/DISCRETE MATH I Topic: Embeddings of Discrete Groups and the Speed of Random Walks Speaker: Assaf Naor Affiliation: Courant Institute Date: Monday, April 14 Time/Room: 11:15am - 12:15pm/S-101

Let G be a finitely generated group equipped with the word metric. Assume that G does not admit a bi-Lipschitz embedding into Hilbert space. How can we quantify the extent to which G is non-Hilbertian? A natural approach is to consider the Hilbert compression exponent of G , i.e. the supremum over all s > 0 such that there exists c > 0 and a Lipschitz mapping f:G --> L_2 such that for all x,y\in G we have ||f(x)-f(y)||\ge c d(x,y)^s . The Hilbert compression exponent of G is clearly independent of the choice of generating set. In this talk we will discuss ways to compute this invariant via a variety of probabilistic and multiscale methods. Joint work with Yuval Peres.