Greg Bodwin

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 76

Top Topics

Strongly Connected Components

Top Venues

Publications

Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu
Additive Spanner Lower Bounds with Optimal Inner Graph Structure. CoRR (2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, Chen Wang
The Discrepancy of Shortest Paths. ICALP (2024)
Aaron Bernstein, Greg Bodwin, Nicole Wein
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? ITCS (2024)
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu
Additive Spanner Lower Bounds with Optimal Inner Graph Structure. ICALP (2024)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM J. Comput. 53 (2) (2024)
Greg Bodwin
An Alternate Proof of Near-Optimal Light Spanners. SOSA (2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, Chen Wang
The Discrepancy of Shortest Paths. CoRR (2024)
Greg Bodwin, Henry L. Fleischmann
Spanning Adjacency Oracles in Sublinear Time. ITCS (2024)
Greg Bodwin, Jeremy Flics
A Lower Bound for Light Spanners in General Graphs. CoRR (2024)
Greg Bodwin, Bernhard Haeupler, Merav Parter
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. SODA (2024)
Greg Bodwin, Michael Dinitz, Yasamin Nazari
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. ITCS (2023)
Greg Bodwin, Gary Hoppenworth
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. FOCS (2023)
Greg Bodwin, Henry Fleischmann
Spanning Adjacency Oracles in Sublinear Time. CoRR (2023)
Greg Bodwin
An Alternate Proof of Near-Optimal Light Spanners. CoRR (2023)
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
Bridge Girth: A Unifying Notion in Network Design. FOCS (2023)
Greg Bodwin, Gary Hoppenworth
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. CoRR (2023)
Aaron Bernstein, Greg Bodwin, Nicole Wein
Are there graphs whose shortest path structure requires large edge weights? CoRR (2023)
Greg Bodwin, Lily Wang
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths. CoRR (2023)
Greg Bodwin, Bernhard Haeupler, Merav Parter
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. CoRR (2023)
Greg Bodwin, Forest Zhang
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. ITCS (2023)
Greg Bodwin, Merav Parter
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. J. ACM 70 (5) (2023)
Greg Bodwin, Forest Zhang
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. CoRR (2022)
Greg Bodwin, Gary Hoppenworth
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. CoRR (2022)
Greg Bodwin, Gary Hoppenworth
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. FOCS (2022)
Greg Bodwin, Michael Dinitz, Yasamin Nazari
Epic Fail: Emulators can tolerate polynomially many edge faults for free. CoRR (2022)
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
Bridge Girth: A Unifying Notion in Network Design. CoRR (2022)
Greg Bodwin
A note on distance-preserving graph sparsification. Inf. Process. Lett. 174 (2022)
Greg Bodwin, Michael Dinitz, Yasamin Nazari
Vertex Fault-Tolerant Emulators. ITCS (2022)
Greg Bodwin, Santosh S. Vempala
A unified view of graph regularity via matrix decompositions. Random Struct. Algorithms 61 (1) (2022)
Greg Bodwin, Michael Dinitz, Caleb Robelle
Partially Optimal Edge Fault-Tolerant Spanners. SODA (2022)
Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence
On Additive Spanners in Weighted Graphs with Local Error. WG (2021)
Greg Bodwin
New Results on Linear Size Distance Preservers. SIAM J. Comput. 50 (2) (2021)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov, Richard Spence
Multi-Level Weighted Additive Spanners. SEA (2021)
Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence
Weighted Sparse and Lightweight Spanners with Local Additive Error. CoRR (2021)
Greg Bodwin, Merav Parter
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. PODC (2021)
Greg Bodwin, Michael Dinitz, Caleb Robelle
Partially Optimal Edge Fault-Tolerant Spanners. CoRR (2021)
Greg Bodwin, Virginia Vassilevska Williams
Better Distance Preservers and Additive Spanners. ACM Trans. Algorithms 17 (4) (2021)
Greg Bodwin, Merav Parter
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. CoRR (2021)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov, Richard Spence
Multi-level Weighted Additive Spanners. CoRR (2021)
Greg Bodwin, Michael Dinitz, Yasamin Nazari
Vertex Fault-Tolerant Emulators. CoRR (2021)
Greg Bodwin, Michael Dinitz, Caleb Robelle
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. SODA (2021)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence
Weighted Additive Spanners. CoRR (2020)
Greg Bodwin, Ofer Grossman
Strategy-Stealing Is Non-Constructive. ITCS (2020)
Greg Bodwin, Keerti Choudhary, Merav Parter, Noa Shahar
New Fault Tolerant Subset Preservers. ICALP (2020)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, Richard Spence
Graph spanners: A tutorial review. Comput. Sci. Rev. 37 (2020)
Greg Bodwin, Michael Dinitz, Caleb Robelle
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. CoRR (2020)
Greg Bodwin
Some General Structure for Extremal Sparsification Problems. CoRR (2020)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence
Weighted Additive Spanners. WG (2020)
Greg Bodwin, Ofer Grossman
Strategy-Stealing is Non-Constructive. CoRR (2019)
Greg Bodwin, Ofer Grossman
Strategy-Stealing is Non-Constructive. Electron. Colloquium Comput. Complex. 26 (2019)
Greg Bodwin, Santosh S. Vempala
Matrix Decompositions and Sparse Graph Regularity. CoRR (2019)
Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, Richard Spence
Graph Spanners: A Tutorial Review. CoRR (2019)
Greg Bodwin
On the Structure of Unique Shortest Paths in Graphs. SODA (2019)
Greg Bodwin, Shyamal Patel
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners. PODC (2019)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47 (6) (2018)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SODA (2018)
Greg Bodwin, Shyamal Patel
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners. CoRR (2018)
Greg Bodwin
On the Structure of Unique Shortest Paths in Graphs. CoRR (2018)
Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams
Optimal Vertex Fault Tolerant Spanners (for fixed stretch). SODA (2018)
Amir Abboud, Greg Bodwin
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. CoRR (2017)
Greg Bodwin
Testing Core Membership in Public Goods Economies. ICALP (2017)
Amir Abboud, Greg Bodwin
The 4/3 Additive Spanner Exponent Is Tight. J. ACM 64 (4) (2017)
Greg Bodwin
Linear Size Distance Preservers. SODA (2017)
Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams
Optimal Vertex Fault Tolerant Spanners (for fixed stretch). CoRR (2017)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA (2017)
Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams
Preserving Distances in Very Faulty Graphs. ICALP (2017)
Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams
Preserving Distances in Very Faulty Graphs. CoRR (2017)
Greg Bodwin
Testing Core Membership in Public Goods Economies. CoRR (2017)
Amir Abboud, Greg Bodwin, Seth Pettie
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR (2016)
Greg Bodwin, Virginia Vassilevska Williams
Better Distance Preservers and Additive Spanners. SODA (2016)
Amir Abboud, Greg Bodwin
The 4/3 additive spanner exponent is tight. STOC (2016)
Greg Bodwin
Linear Size Distance Preservers. CoRR (2016)
Greg Bodwin, Sebastian Krinninger
Fully Dynamic Spanners with Worst-Case Update Time. CoRR (2016)
Greg Bodwin, Sebastian Krinninger
Fully Dynamic Spanners with Worst-Case Update Time. ESA (2016)
Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, Morten Stöckel
Graph Reconstruction with a Betweenness Oracle. STACS (2016)
Amir Abboud, Greg Bodwin
Error Amplification for Pairwise Spanner Lower Bounds. SODA (2016)
Amir Abboud, Greg Bodwin
The 4/3 Additive Spanner Exponent is Tight. CoRR (2015)