We partially prove a conjecture that was raised by Linial, London and Rabinovich in 1994. Let G be a k-regular graph, k > 2, with girth g. We show that every embedding of G to the Euclidean space has distortion Omega(g^.5). The original conjecture which remains open is that the Euclidean distortion is bounded below by Omega(g). Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.
Joint work with Nati Linial and Assaf Naor.