Selected Publications

The 4/3 Additive Spanner Exponent is Tight

(STOC 2016 Best Student Paper, Full Version JACM 2017, Invited to HALG 2016 & SODM 2018), by Amir Abboud and Greg Bodwin

On the Structure of Unique Shortest Paths in Graphs

(SODA 2019, Invited to HALG 2019), by Greg Bodwin

Linear Size Distance Preservers

(SODA 2017), by Greg Bodwin

A Unified View of Sparse Graph Regularity via Matrix Decompositions

(preprint), by Greg Bodwin and Santosh Vempala

All Publications

A Note on Distance-Preserving Graph Sparsification

(preprint), by Greg Bodwin

A Unified View of Sparse Graph Regularity via Matrix Decompositions

(preprint), by Greg Bodwin and Santosh Vempala

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

(SODA 2021), by Greg Bodwin, Michael Dinitz, and Caleb Robelle

New Fault Tolerant Subset Preservers

(ICALP 2020), by Greg Bodwin, Keerti Choudhary, Merav Parter, and Noa Shahar

Weighted Additive Spanners

(WG 2020), by Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, and Richard Spence

Strategy-Stealing is Non-Constructive

(ITCS 2020), by Greg Bodwin and Ofer Grossman

A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

(PODC 2019), by Greg Bodwin and Shyamal Patel

On the Structure of Unique Shortest Paths in Graphs

(SODA 2019, invited to HALG 2019), by Greg Bodwin

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

(SODA 2018), by Amir Abboud and Greg Bodwin

Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

(SODA 2018), by Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams

Preserving Distances in Very Faulty Graphs

(ICALP 2017), by Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams

Testing Core Membership in Public Goods Economies

(ICALP 2017), by Greg Bodwin

Linear Size Distance Preservers

(SODA 2017), by Greg Bodwin

A Hierarchy of Lower Bounds for Sublinear Additive Spanners

(SODA 2017, Full Version SICOMP 2018), by Amir Abboud, Greg Bodwin, and Seth Pettie

Fully Dynamic Spanners with Worst-Case Update Time

(ESA 2017), by Greg Bodwin and Sebastian Krinninger

The 4/3 Additive Spanner Exponent is Tight

(STOC 2016 Best Student Paper, Full Version JACM 2017, Invited to HALG 2016 & SODM 2018), by Amir Abboud and Greg Bodwin

Graph Reconstruction with a Betweenness Oracle

(STACS 2016), by Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel

Error Amplification for Pairwise Spanner Lower Bounds

(SODA 2016), by Amir Abboud and Greg Bodwin

Better Distance Preservers and Additive Spanners

(SODA 2016), by Greg Bodwin and Virginia Vassilevska Williams

Very Sparse Additive Spanners and Emulators

(ITCS 2015), by Greg Bodwin and Virginia Vassilevska Williams

Thesis, Notes, Surveys

Graph Spanners: A Tutorial Review

(Computer Science Review 2020), by Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Richard Spence

Sketching Distances in Graphs

(Ph.D. Thesis, winner of George M. Sprowls Award for best MIT EECS thesis of the year), by Greg Bodwin