Gregory Bodwin

According to our database, Gregory Bodwin authored at least 45 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Reachability Preservers: New Extremal Bounds and Approximation Algorithms.

Amir Abboud, Greg Bodwin

SIAM J. Comput., 2024

Improved Online Reachability Preservers.

Greg Bodwin, Tuong Le

CoRR, 2024

A Lower Bound for Light Spanners in General Graphs.

Greg Bodwin, Jeremy Flics

CoRR, 2024

An Alternate Proof of Near-Optimal Light Spanners.

Greg Bodwin

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

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

Greg Bodwin, Bernhard Haeupler, Merav Parter

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Spanning Adjacency Oracles in Sublinear Time.

Greg Bodwin, Henry L. Fleischmann

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?

Aaron Bernstein, Greg Bodwin, Nicole Wein

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Additive Spanner Lower Bounds with Optimal Inner Graph Structure.

Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

The Discrepancy of Shortest Paths.

Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, Chen Wang

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs.

Greg Bodwin, Merav Parter

J. ACM, October, 2023

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

Greg Bodwin, Lily Wang

CoRR, 2023

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

Greg Bodwin, Forest Zhang

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free.

Greg Bodwin, Michael Dinitz, Yasamin Nazari

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Bridge Girth: A Unifying Notion in Network Design.

Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

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

Greg Bodwin, Gary Hoppenworth

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

A unified view of graph regularity via matrix decompositions.

Greg Bodwin, Santosh S. Vempala

Random Struct. Algorithms, 2022

A note on distance-preserving graph sparsification.

Greg Bodwin

Inf. Process. Lett., 2022

Partially Optimal Edge Fault-Tolerant Spanners.

Greg Bodwin, Michael Dinitz, Caleb Robelle

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Vertex Fault-Tolerant Emulators.

Greg Bodwin, Michael Dinitz, Yasamin Nazari

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

New Additive Spanner Lower Bounds by an Unlayered Obstacle Product.

Greg Bodwin, Gary Hoppenworth

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Better Distance Preservers and Additive Spanners.

Greg Bodwin, Virginia Vassilevska Williams

ACM Trans. Algorithms, 2021

New Results on Linear Size Distance Preservers.

Greg Bodwin

SIAM J. Comput., 2021

Weighted Sparse and Lightweight Spanners with Local Additive Error.

Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence

CoRR, 2021

On Additive Spanners in Weighted Graphs with Local Error.

Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Multi-Level Weighted Additive Spanners.

Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov, Richard Spence

Proceedings of the 19th International Symposium on Experimental Algorithms, 2021

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time.

Greg Bodwin, Michael Dinitz, Caleb Robelle

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Graph spanners: A tutorial review.

Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, Richard Spence

Comput. Sci. Rev., 2020

Some General Structure for Extremal Sparsification Problems.

Greg Bodwin

CoRR, 2020

Weighted Additive Spanners.

Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

New Fault Tolerant Subset Preservers.

Greg Bodwin, Keerti Choudhary, Merav Parter, Noa Shahar

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Strategy-Stealing is Non-Constructive.

Greg Bodwin, Ofer Grossman

Electron. Colloquium Comput. Complex., 2019

Matrix Decompositions and Sparse Graph Regularity.

Greg Bodwin, Santosh S. Vempala

CoRR, 2019

On the Structure of Unique Shortest Paths in Graphs.

Greg Bodwin

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners.

Greg Bodwin, Shyamal Patel

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018

Sketching distances in graphs.

Gregory Michael Bodwin

PhD thesis, 2018

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.

Amir Abboud, Greg Bodwin, Seth Pettie

SIAM J. Comput., 2018

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

The 4/3 Additive Spanner Exponent Is Tight.

Amir Abboud, Greg Bodwin

J. ACM, 2017

Linear Size Distance Preservers.

Greg Bodwin

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Preserving Distances in Very Faulty Graphs.

Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Testing Core Membership in Public Goods Economies.

Greg Bodwin

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Graph Reconstruction with a Betweenness Oracle.

Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, Morten Stöckel

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Error Amplification for Pairwise Spanner Lower Bounds.

Amir Abboud, Greg Bodwin

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Fully Dynamic Spanners with Worst-Case Update Time.

Greg Bodwin, Sebastian Krinninger

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Very Sparse Additive Spanners and Emulators.

Gregory Bodwin, Virginia Vassilevska Williams

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015