Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Deterministic Online embedding of metrics
Ilan Newman (University of Haifa)
Wednesday, 20.03.2024, 13:15
Taub 201
A finite metric space \$(X,d)\$ on a set of points \$X\$ is just the shortest path metric \$d\$ on a positively weighted graph \$G=(X,E)\$. In the online setting, the vertices of the input finite metric space \$(X,d)\$ are exposed one by one, together with their distances \$d(*,*)\$

to the previously exposed vertices. The goal is to embed (map) \$X\$ into a given host metric space \$(H,d_H)\$ (finite or not) and so to distort the distances as little as possible (distortion is the worst case ratio of how the distance is expanded, assuming it is never contracted).

I will start by a short survey on the main existing results of offline embedding into \$ell_1, ell_2, ell_{infty}\$ spaces. Then will present some results on online embedding: mainly lower bounds (on the best distortion) for small dimensional spaces, and some upper bounds for 2-dim Euclidean spaces.

As an intriguing question: the "rigid" \$K_5\$ metric space is a metric space on \$G=K_5\$, in which each edge should be thought as a unit interval \$[0,1]\$. The points are the \$5\$ fixed vertices of \$K_5\$ (that are exposed first) in addition to \$n\$ points that are arbitrarily placed anywhere in the edges, and exposed one by one. It is easy to show that an offline embedding into the \$2\$-dim Euclidean results in a distortion \$Omega(n)\$. What can be achieved in the online case ?? It was "believed" that an exponential distortion could be proven. We show that the distortion is bounded by \$O(n^2)\$.

The talk is based on joint work with Noam Licht and Yuri Rabinovich