Theory Seminar
Zihan Tan: Almost-Optimal Sublinear Additive Spanners
WHERE:
3725 Beyster Building
WHEN:
Friday, April 14, 2023 @ 3:00 pm - 4:00 pm
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
SHARE:
Given an undirected unweighted graph G=(V, E) on n vertices and m edges, a subgraph H is a spanner of G with stretch function f, iff for every pair s, t of vertices, dist_H(s,t) is at most f(dist_G(s,t)). When f(d)=d+o(d), H is called a sublinear additive spanner. In this talk, we show that for any constant integer k>=2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^{1-1/k}) and O(n^{1+1/(2^{k+1}-1)+o(1)}) edges. The size bound of our spanners almost matches the lower bound proved in [Abboud-Bodwin-Pettie 2017], which holds for any data structure that maintains distances within the same stretch function.
This talk is based on joint work with Tianyi Zhang.