Zihan Tan: Almost-Optimal Sublinear Additive Spanners

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.