4 papers
Multiplicative Spanners in Minor-Free Graphs
Greg Bodwin, Gary Hoppenworth, Zihan Tan
In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $…
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2
We construct -node graphs on which any -size spanner has additive error at least , improving on the previous best lower bound of [Bodwin-Hoppe…
The Discrepancy of Shortest Paths
Greg Bodwin, Chengyuan Deng, Jie Gao +3
The hereditary discrepancy of a set system is a certain quantitative measure of the pseudorandom properties of the system. Roughly, hereditary discrepancy measures how well one can…
Folklore Sampling is Optimal for Exact Hopsets: Confirming the Barrier
Greg Bodwin, Gary Hoppenworth
For a graph , a -diameter-reducing exact hopset is a small set of additional edges that, when added to , maintains its graph metric but guarantees that all node pairs…