A Hierarchy of Lower Bounds for Sublinear Additive Spanners

Amir Abboud, Greg Bodwin, Seth Pettie

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta })$…