ICALP 2023

New Additive Emulators

Jul 11, 2023, 10:55 AM

20m

Seminar Room 4 (HNF)

Track A-2

Speaker

Merav Parter

Description

Shimon Kogan and Merav Parter

Abstract: The only known upper bound for this problem is given by an implicit construction of
[Pettie, ICALP 2007] that provides a linear-size emulator with $+\tilde{O}(n^{1/4})$ stretch. No improvement on this problem has been shown since then.

In this work we improve upon the long standing additive stretch of $\tilde{O}(n^{1/4})$, by presenting constructions of linear-size emulators with $\tilde{O}(n^{0.222})$ additive stretch. Our constructions improve the state-of-the-art size vs.\ stretch tradeoff in the entire regime. For example, for every $ϵ>1/7$, we provide $+n^{f(ϵ)}$ emulators of size $\tilde{O}(n^{1+ϵ})$, for $f(ϵ)=1/5-3ϵ/5$. This should be compared with the current bound of $f(ϵ)=1/4-3ϵ/4$ by [Pettie, ICALP 2007].

The new emulators are based on an extended and optimized toolkit for computing weighted additive emulators with sublinear distance error. Our key construction provides a weighted modification of the well-known Thorup and Zwick emulators [SODA 2006]. We believe that this TZ variant might be of independent interest, especially for providing improved stretch for distant pairs.