Combinatorics Seminar

When: Sunday, November 15, 10am Where: Schreiber 309 Speaker: Ilan Newman, University of Haifa Title: The Cut dimension of l_1-metrics, sparsification techniques and l_1 volumes

Abstract:

The celebrated Johnson-Lindenstrauss results states that any Euclidean metric on n points can be embedded in O(\log n/\epsilon^2)-dimensional space with distortion at most 1+ \epsilon).

The situation for l_1 metrics is quite different from that of l_2 metrics. The results of Brikman-Charikar and Lee-Naor show that one cannot expect dimension reduction better than d=n^{1/D^2} if one is prepared to accept distortion bounded by D. The best upper bound on the dimension, for any constant distortion is O(n\log n), due to Schechtman. The gap between the lower and upper bound is open at large.

We note that by employing results on graph sparsification of Karger-Benczur and Spielmann-Teng-Batson-Srivastava one can show that every l_1 metric can be approximated by embedding into O(n) dimensional l_1 space. We further study these methods and show that they generalize considerably.

In particular, this has leads us to new definitions of finite volume spaces, and their l_1 counterparts. We show that dimension reduction works for such objects too.

This is a joint work with Yuri Rabinovich.