Online Monotone Metric Embeddings
- Yichen Huang, Harvard University
- Time: 2026-05-28 15:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
Metric embeddings into structured spaces, particularly hierarchically well-separated trees (HSTs), are a fundamental tool in the design of online algorithms. In the classical online embedding setting, points arrive sequentially and must be embedded irrevocably upon arrival, resulting in strong distortion lower bounds of $\Omega(\min(n, \log n\log \Delta))$, where $n$ is the number of points and $\Delta$ their aspect ratio.
We propose a novel relaxation, online monotone metric embeddings, which allows distances between embedded points in the target space to decrease monotonically over time. Such relaxed embeddings remain compatible with many online algorithms. Moreover, this relaxation breaks existing lower bound barriers, enabling embeddings into HSTs with distortion $O(\log^2 n)$.
Time permitting, I will also explain a fully dynamic variant, where points may both arrive and depart, seeking distortion guarantees in terms of the maximum number $l$ of simultaneously present points. For traditional embeddings, such bounds are impossible, and this limitation persists even for deterministic monotone embeddings. Surprisingly, probabilistic monotone embeddings allow for $O(l \log l)$ distortion, which is nearly optimal given an $\Omega(l)$ lower bound.
Based on joint work with Christian Coester.
Biography
Yichen Huang is a second-year PhD student at Harvard University, advised by Professor Michael Mitzenmacher. His research interests focus on decision-making under uncertainty, including online algorithms, learning-augmented algorithms, and mechanism design.