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
An Alternate Proof of Near-Optimal Light Spanners
(SOSA 2024 Best Paper), by Greg Bodwin
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
(PODC 2021 Best Paper, Invited to HALG 2022, Full Version JACM 2023), by Greg Bodwin and Merav Parter
Folklore Sampling is Optimal for Exact Hopsets
(FOCS 2023), by Greg Bodwin and Gary Hoppenworth
All Publications
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
(preprint), by Greg Bodwin and Lily Wang
Spanning Adjacency Oracles in Sublinear Time
(ITCS 2024), by Greg Bodwin and Henry Fleischmann
Are there graphs whose shortest path structure requires large edge weights?
(ITCS 2024), by Aaron Bernstein, Greg Bodwin, and Nicole Wein
An Alternate Proof of Near-Optimal Light Spanners
(SOSA 2024 Best Paper), by Greg Bodwin
Folklore Sampling is Optimal for Exact Hopsets
(FOCS 2023), by Greg Bodwin and Gary Hoppenworth
Bridge Girth: A Unifying Notion in Network Design
(FOCS 2023), by Greg Bodwin, Gary Hoppenworth, and Ohad Trabelsi
Epic Fail: Emulators can tolerate polynomially many edge faults for free
(ITCS 2023), by Greg Bodwin, Michael Dinitz, and Yasamin Nazari
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
(ITCS 2023), by Greg Bodwin and Forest Zhang
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
(FOCS 2022), by Greg Bodwin and Gary Hoppenworth
Vertex Fault-Tolerant Emulators
(ITCS 2022), by Greg Bodwin, Michael Dinitz, and Yasamin Nazari
Partially Optimal Edge Fault-Tolerant Spanners
(SODA 2022), by Greg Bodwin, Michael Dinitz, and Caleb Robelle
A Note on Distance-Preserving Graph Sparsification
(IPL 2021), by Greg Bodwin
A Unified View of Sparse Graph Regularity via Matrix Decompositions
(RSA 2021), by Greg Bodwin and Santosh Vempala
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
(PODC 2021 Best Paper, Invited to HALG 2022, Full Version JACM 2023), by Greg Bodwin and Merav Parter
Weighted Sparse and Lightweight Spanners with Local Additive Error
(WG 2021), by Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence
Multi-level Weighted Additive Spanners
(SEA 2021), by Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence
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
New Results on Linear Size Distance Preservers
(SODA 2017, Full Version SICOMP 2021), 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 2016), 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, Full Version TALG 2021), 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