Theory Seminar, Wednesday May 6: Avi Kadria (BIU) - Faster Algorithms for (2k-1)-Stretch Distance Oracles

[Arnold Filtser]

Hi all,

Next week (Wednesday May 6, at 12pm) we will meet for our theory seminar. The talk will be by Avi Kadria (see details below).

After Avi's talk, we will have an additional talk by Nir Akay on the paper "Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation" (see  https://arxiv.org/pdf/2302.02567).

Location: Building 503 room 226.

Looking forward to seeing you all there,
Arnold
https://theory.cs.biu.ac.il/


Speaker: Avi Kadria (BIU)
Title:  Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
Abstract: 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 5-stretch oracle in truly subquadratic time, 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.

[Arnold Filtser]

The talk starts in one hour!