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.