Computer Science/Discrete Mathematics Seminar I

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.