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.