TITLE: Embedding into $l_p$ with constant average distortion
SPEAKER: Ofer Neinman, Hebrew University of Jerusalem
WHEN: 12:00-13:00, October 20
WHERE: Wean Hall 5403
ABSTRACT:
An embedding is a function between metric spaces, usualy from an arbitrary one into a more simple and structured space (such a Euclidean space). The distortion is the multiplicative amount by which distances change. A well known theorem of Bourgain states that every metric space embeds into Euclidean space with $O(\log n)$ distortion, which is tight. Our result is a strengthening of Bourgain’s Theorem, providing a CO-Lipschitz embedding with constant average distortion. As a matter of fact, it provides for any $\epsilon$ the best $\epsilon$-slack distortion simultaneously.
This is joint work with Yair Bartal and Ittai Abraham.
