Ilan Newman

Deterministic Online Embedding of Metric Spaces into Low Dimensional Spaces

We study online embeddings of metric spaces into Euclidean spaces of a constant dimension $d>1$, against an adaptive adversary. While the case of $d=1$ is well understood, for higher dimensions little is known. In particular, even for $d=2$ it remains unknown whether the worst-case distortion grows exponentially with t...