2 citations · 3 across the 10 of their papers we have counts for
15 papers
Simple Length-Constrained Expander Decompositions
Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz +1
Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an -length -expa…
Notes on the Linear Algebraic View of Regularity Lemmas
Greg Bodwin, Tuong Le
When regularity lemmas were first developed in the 1970s, they were described as results that promise a partition of any graph into a ``small'' number of parts, such that the graph…
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 $…
Light Edge Fault Tolerant Graph Spanners
Greg Bodwin, Michael Dinitz, Ama Koranteng +1
There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work h…
Improved Online Reachability Preservers
Greg Bodwin, Tuong Le
A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an -node directed input graph among a set of given demand pairs $P…
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-Hoppenw…
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…
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
Greg Bodwin, Bernhard Haeupler, Merav Parter
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a…
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
Greg Bodwin, Lily Wang
The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [PODC '01], which relates the structure of shortest paths in a graph before and afte…
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
Greg Bodwin, Merav Parter
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a f…
A Unified View of Graph Regularity via Matrix Decompositions
Greg Bodwin, Santosh Vempala
We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
Greg Bodwin, Shyamal Patel
We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faul…
The 4/3 Additive Spanner Exponent is Tight
Amir Abboud, Greg Bodwin
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a…
Very Sparse Additive Spanners and Emulators
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…
Better Distance Preservers and Additive Spanners
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…