Theory Lunch This Thursday (10/24) at 12:00 in SAL 322

[Grayson York]

Hi all,

Please join us for theory lunch this Thursday, where Neel will be giving the following talk.

Thanks,

Grayson

Title: Near-Optimal $(1+\epsilon)$-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

Joint work with Arnold Filtser, Gramoz Goranci and Maximilian Probst Gutenberg

Abstract: 

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an $n$-vertex planar graph $G=(V,E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a $(1+\epsilon)$-approximate dynamic algorithm that supports edge updates and distance queries in $n^{o(1)}$ time, for any $1/\text{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of $\tilde{O}(\sqrt{n})$ on update and query time due to [Abraham, Chechik, and Gavoille, STOC '12], and bypasses a $\Omega(\sqrt{n})$ conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS '16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC '22].

[Grayson York]

Hi all,

Please join us at the following zoom link:

https://us04web.zoom.us/j/77231469836?pwd=7Hw7HTxUCQeltqbuQ8qB5cLSZp0U1B.1

Thanks,

Grayson

[Grayson York]

https://us04web.zoom.us/j/77519826461?pwd=sgdCO6YHhgzCaX7LV7s6bkxlvFktct.1