CS Peer Talk | Online Monotone Metric Embeddings

报告人：Yichen Huang, Harvard University

时间：5月28日（星期四）3:00pm

地点：静园五院204

Host：楼家宁，图灵班2019级

Online Monotone Metric Embeddings

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    , where  is the number of points and  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  .

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    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  distortion, which is nearly optimal given an  lower bound.

Based on joint work with Christian Coester.

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.

北京大学图灵班科研活动委员会