[Mittagsseminar TI] Mittagsseminar am 28.19.2025

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

       Dienstag, 28.10.2025, 12:00 Uhr, SR 055, Takustraße 9
       Avi Kardia
       zum Thema: Faster Algorithms for (2k-1)-Stretch Distance Oracles

Distance oracles are compact data structures that approximate shortest 
paths efficiently. Since the seminal work of Thorup and Zwick, the main 
challenge has been to build them fast, without losing the optimal 
stretch–space tradeoff.

In this talk, I will present new algorithms that break longstanding 
barriers in preprocessing time. In particular, I will focus on our 
construction of a (2k−1)-stretch oracle in truly subquadratic time for
k=3, resolving an open problem raised by Wulff-Nilsen. The key 
ingredient is a new hierarchy of parameterized distance oracles, which 
allows us to speed up the construction while maintaining optimal size 
and stretch.

I will also briefly overview how these techniques extend to other ranges 
of k and to unweighted graphs, where we obtain further improvements.

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature