Greg Bodwin

Publications

Google ScholarDBLP

Selected Publications

  1. 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

  2. On the Structure of Unique Shortest Paths in Graphs

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

  3. An Alternate Proof of Near-Optimal Light Spanners

    [Lean formalization]

    (SOSA 2024 Best Paper, full version TheoretiCS 2025, invited to HALG 2025), by Greg Bodwin

  4. 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

  5. Folklore Sampling is Optimal for Exact Hopsets

    (FOCS 2023, invited to HALG 2024), by Greg Bodwin and Gary Hoppenworth

Research Publications

  1. Unconditional Lower Bounds for Degree Fault Tolerant Spanners

    [Lean formalization]

    (ESA 2026), by Greg Bodwin and Aleksey Lopez

  2. Improved Upper Bounds for the Directed Flow-Cut Gap

    (FOCS 2026), by Greg Bodwin and Luba Samborska

  3. Simple Length-Constrained Expander Decompositions

    [Lean formalization]

    (SOSA 2026), by Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan

  4. Greedy Algorithms for Shortcut Sets and Hopsets

    (Preprint 2025), by Ben Bals, Joakim Blikstad, Greg Bodwin, Daniel Dadush, Sebastian Forster, and Yasamin Nazari

  5. Multiplicative Spanners in Minor-Free Graphs

    [Lean formalization]

    (Preprint 2025), by Greg Bodwin, Gary Hoppenworth, and Zihan Tan

  6. Light Edge Fault Tolerant Graph Spanners

    (ICALP 2025), by Greg Bodwin, Michael Dinitz, Ama Koranteng, and Lily Wang

  7. Improved Online Reachability Preservers

    (SODA 2025), by Greg Bodwin and Tuong Le

  8. A Lower Bound for Light Spanners in General Graphs

    (SODA 2025), by Greg Bodwin and Jeremy Flics

  9. Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths

    (SODA 2025), by Greg Bodwin and Lily Wang

  10. Additive Spanner Lower Bounds with Optimal Inner Graph Structure

    (ICALP 2024), by Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu

  11. The Discrepancy of Shortest Paths

    (ICALP 2024), by Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang

  12. Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

    (SODA 2024), by Greg Bodwin, Bernhard Haeupler, and Merav Parter

  13. Spanning Adjacency Oracles in Sublinear Time

    (ITCS 2024), by Greg Bodwin and Henry Fleischmann

  14. Are there graphs whose shortest path structure requires large edge weights?

    (ITCS 2024), by Aaron Bernstein, Greg Bodwin, and Nicole Wein

  15. An Alternate Proof of Near-Optimal Light Spanners

    [Lean formalization]

    (SOSA 2024 Best Paper, full version TheoretiCS 2025, invited to HALG 2025), by Greg Bodwin

  16. Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier

    (FOCS 2023, invited to HALG 2024), by Greg Bodwin and Gary Hoppenworth

  17. Bridge Girth: A Unifying Notion in Network Design

    (FOCS 2023), by Greg Bodwin, Gary Hoppenworth, and Ohad Trabelsi

  18. Opponent Indifference in Rating Systems: A Theoretical Case for Sonas

    (ITCS 2023), by Greg Bodwin and Forest Zhang

  19. Epic Fail: Emulators can tolerate polynomially many edge faults for free

    (ITCS 2023), by Greg Bodwin, Michael Dinitz, and Yasamin Nazari

  20. New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

    (FOCS 2022), by Greg Bodwin and Gary Hoppenworth

  21. Vertex Fault-Tolerant Emulators

    (ITCS 2022), by Greg Bodwin, Michael Dinitz, and Yasamin Nazari

  22. Partially Optimal Edge Fault-Tolerant Spanners

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

  23. A Note on Distance-Preserving Graph Sparsification

    [Lean formalization]

    (Information Processing Letters 2022), by Greg Bodwin

  24. A Unified View of Graph Regularity via Matrix Decompositions

    (Random Structures & Algorithms 2022), by Greg Bodwin and Santosh Vempala

  25. Weighted Sparse and Lightweight Spanners with Local Additive Error

    (WG 2021), by Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, and Richard Spence

  26. 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

  27. Multi-level Weighted Additive Spanners

    (SEA 2021), by Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, and Richard Spence

  28. Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

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

  29. New Fault Tolerant Subset Preservers

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

  30. Weighted Additive Spanners

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

  31. Strategy-Stealing is Non-Constructive

    (ITCS 2020), by Greg Bodwin and Ofer Grossman

  32. A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

    [Lean formalization]

    (PODC 2019), by Greg Bodwin and Shyamal Patel

  33. On the Structure of Unique Shortest Paths in Graphs

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

  34. Reachability Preservers: New Extremal Bounds and Approximation Algorithms

    (SODA 2018, full version SICOMP 2024), by Amir Abboud and Greg Bodwin

  35. Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

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

  36. Testing Core Membership in Public Goods Economies

    (ICALP 2017), by Greg Bodwin

  37. Preserving Distances in Very Faulty Graphs

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

  38. A Hierarchy of Lower Bounds for Sublinear Additive Spanners

    (SODA 2017, full version SICOMP 2018), by Amir Abboud, Greg Bodwin, and Seth Pettie

  39. New Results on Linear Size Distance Preservers

    [Lean formalization]

    (SODA 2017, full version SICOMP 2021), by Greg Bodwin

  40. Fully Dynamic Spanners with Worst-Case Update Time

    (ESA 2016), by Greg Bodwin and Sebastian Krinninger

  41. Graph Reconstruction with a Betweenness Oracle

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

  42. Error Amplification for Pairwise Spanner Lower Bounds

    (SODA 2016), by Amir Abboud and Greg Bodwin

  43. 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

  44. Better Distance Preservers and Additive Spanners

    (SODA 2016, full version TALG 2021), by Greg Bodwin and Virginia Vassilevska Williams

  45. Very Sparse Additive Spanners and Emulators

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

Notes, Thesis, and Surveys

  1. Notes on the Linear Algebraic View of Regularity Lemmas

    (Notes 2025), by Greg Bodwin and Tuong Le

  2. 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, and Richard Spence

  3. Sketching Distances in Graphs

    (Ph.D. Thesis, MIT 2018; George M. Sprowls Award), by Greg Bodwin