default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDGregory Bodwin
Person information
- affiliation (PhD 2018): Massachusetts Institute of Technology, Cambridge, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
[j9]Amir Abboud, Greg Bodwin
:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM J. Comput. 53(2): 221-246 (2024)- [c34]Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, Chen Wang:
The Discrepancy of Shortest Paths. ICALP 2024: 27:1-27:20 - [c33]Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu:
Additive Spanner Lower Bounds with Optimal Inner Graph Structure. ICALP 2024: 28:1-28:17 - [c32]Aaron Bernstein, Greg Bodwin, Nicole Wein:
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? ITCS 2024: 12:1-12:22 - [c31]Greg Bodwin, Henry L. Fleischmann:
Spanning Adjacency Oracles in Sublinear Time. ITCS 2024: 19:1-19:21 - [c30]Greg Bodwin, Bernhard Haeupler, Merav Parter:
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. SODA 2024: 2609-2642 - [c29]Greg Bodwin:
An Alternate Proof of Near-Optimal Light Spanners. SOSA 2024: 39-55 - [i38]Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, Chen Wang:
The Discrepancy of Shortest Paths. CoRR abs/2401.15781 (2024) - [i37]Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu:
Additive Spanner Lower Bounds with Optimal Inner Graph Structure. CoRR abs/2404.18337 (2024) - [i36]Greg Bodwin, Jeremy Flics:
A Lower Bound for Light Spanners in General Graphs. CoRR abs/2406.04459 (2024) - [i35]Greg Bodwin, Tuong Le:
Improved Online Reachability Preservers. CoRR abs/2410.20471 (2024) - 2023
- [j8]Greg Bodwin, Merav Parter:
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. J. ACM 70(5): 28:1-28:24 (2023) - [c28]Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi:
Bridge Girth: A Unifying Notion in Network Design. FOCS 2023: 600-648 - [c27]Greg Bodwin, Gary Hoppenworth:
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. FOCS 2023: 701-720 - [c26]Greg Bodwin, Michael Dinitz, Yasamin Nazari:
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. ITCS 2023: 20:1-20:22 - [c25]Greg Bodwin, Forest Zhang:
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. ITCS 2023: 21:1-21:21 - [i34]Greg Bodwin, Gary Hoppenworth:
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier. CoRR abs/2304.02193 (2023) - [i33]Greg Bodwin:
An Alternate Proof of Near-Optimal Light Spanners. CoRR abs/2305.18647 (2023) - [i32]Aaron Bernstein, Greg Bodwin, Nicole Wein:
Are there graphs whose shortest path structure requires large edge weights? CoRR abs/2308.13054 (2023) - [i31]Greg Bodwin, Henry L. Fleischmann:
Spanning Adjacency Oracles in Sublinear Time. CoRR abs/2308.13890 (2023) - [i30]Greg Bodwin, Bernhard Haeupler, Merav Parter:
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. CoRR abs/2309.06696 (2023) - [i29]Greg Bodwin, Lily Wang:
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths. CoRR abs/2309.07964 (2023) - 2022
- [j7]Greg Bodwin:
A note on distance-preserving graph sparsification. Inf. Process. Lett. 174: 106205 (2022) - [j6]Greg Bodwin, Santosh S. Vempala:
A unified view of graph regularity via matrix decompositions. Random Struct. Algorithms 61(1): 62-83 (2022) - [c24]Greg Bodwin, Gary Hoppenworth:
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. FOCS 2022: 778-788 - [c23]Greg Bodwin, Michael Dinitz, Yasamin Nazari:
Vertex Fault-Tolerant Emulators. ITCS 2022: 25:1-25:22 - [c22]Greg Bodwin, Michael Dinitz, Caleb Robelle:
Partially Optimal Edge Fault-Tolerant Spanners. SODA 2022: 3272-3286 - [i28]Greg Bodwin, Gary Hoppenworth:
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. CoRR abs/2207.11832 (2022) - [i27]Greg Bodwin, Michael Dinitz, Yasamin Nazari:
Epic Fail: Emulators can tolerate polynomially many edge faults for free. CoRR abs/2209.03675 (2022) - [i26]Greg Bodwin, Forest Zhang:
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. CoRR abs/2209.03950 (2022) - [i25]Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi:
Bridge Girth: A Unifying Notion in Network Design. CoRR abs/2212.11944 (2022) - 2021
- [j5]Greg Bodwin:
New Results on Linear Size Distance Preservers. SIAM J. Comput. 50(2): 662-673 (2021) - [j4]Greg Bodwin, Virginia Vassilevska Williams:
Better Distance Preservers and Additive Spanners. ACM Trans. Algorithms 17(4): 36:1-36:24 (2021) - [c21]Greg Bodwin, Merav Parter:
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. PODC 2021: 435-443 - [c20]Greg Bodwin, Michael Dinitz, Caleb Robelle:
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. SODA 2021: 2924-2938 - [c19]Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov, Richard Spence:
Multi-Level Weighted Additive Spanners. SEA 2021: 16:1-16:23 - [c18]Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence:
On Additive Spanners in Weighted Graphs with Local Error. WG 2021: 361-373 - [i24]Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen G. Kobourov, Richard Spence:
Multi-level Weighted Additive Spanners. CoRR abs/2102.05831 (2021) - [i23]Greg Bodwin, Merav Parter:
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs. CoRR abs/2102.10174 (2021) - [i22]Greg Bodwin, Michael Dinitz, Caleb Robelle:
Partially Optimal Edge Fault-Tolerant Spanners. CoRR abs/2102.11360 (2021) - [i21]Abu Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen G. Kobourov, Richard Spence:
Weighted Sparse and Lightweight Spanners with Local Additive Error. CoRR abs/2103.09731 (2021) - [i20]Greg Bodwin, Michael Dinitz, Yasamin Nazari:
Vertex Fault-Tolerant Emulators. CoRR abs/2109.08042 (2021) - 2020
- [j3]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: 100253 (2020) - [c17]Greg Bodwin, Keerti Choudhary, Merav Parter, Noa Shahar:
New Fault Tolerant Subset Preservers. ICALP 2020: 15:1-15:19 - [c16]Greg Bodwin, Ofer Grossman:
Strategy-Stealing Is Non-Constructive. ITCS 2020: 21:1-21:12 - [c15]Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence:
Weighted Additive Spanners. WG 2020: 401-413 - [i19]Greg Bodwin:
Some General Structure for Extremal Sparsification Problems. CoRR abs/2001.07741 (2020) - [i18]Abu Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence:
Weighted Additive Spanners. CoRR abs/2002.07152 (2020) - [i17]Greg Bodwin, Michael Dinitz, Caleb Robelle:
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. CoRR abs/2007.08401 (2020)
2010 – 2019
- 2019
- [c14]Greg Bodwin, Shyamal Patel:
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners. PODC 2019: 541-543 - [c13]Greg Bodwin:
On the Structure of Unique Shortest Paths in Graphs. SODA 2019: 2071-2089 - [i16]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 abs/1909.03152 (2019) - [i15]Greg Bodwin, Ofer Grossman:
Strategy-Stealing is Non-Constructive. CoRR abs/1911.06907 (2019) - [i14]Greg Bodwin, Santosh S. Vempala:
Matrix Decompositions and Sparse Graph Regularity. CoRR abs/1911.11868 (2019) - [i13]Greg Bodwin, Ofer Grossman:
Strategy-Stealing is Non-Constructive. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [b1]Gregory Michael Bodwin:
Sketching distances in graphs. Massachusetts Institute of Technology, Cambridge, USA, 2018 - [j2]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SIAM J. Comput. 47(6): 2203-2236 (2018) - [c12]Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SODA 2018: 1865-1883 - [c11]Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams:
Optimal Vertex Fault Tolerant Spanners (for fixed stretch). SODA 2018: 1884-1900 - [i12]Greg Bodwin:
On the Structure of Unique Shortest Paths in Graphs. CoRR abs/1804.09745 (2018) - [i11]Greg Bodwin, Shyamal Patel:
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners. CoRR abs/1812.05778 (2018) - 2017
- [j1]Amir Abboud, Greg Bodwin:
The 4/3 Additive Spanner Exponent Is Tight. J. ACM 64(4): 28:1-28:20 (2017) - [c10]Greg Bodwin:
Testing Core Membership in Public Goods Economies. ICALP 2017: 45:1-45:14 - [c9]Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams:
Preserving Distances in Very Faulty Graphs. ICALP 2017: 73:1-73:14 - [c8]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. SODA 2017: 568-576 - [c7]Greg Bodwin:
Linear Size Distance Preservers. SODA 2017: 600-615 - [i10]Greg Bodwin, Fabrizio Grandoni, Merav Parter, Virginia Vassilevska Williams:
Preserving Distances in Very Faulty Graphs. CoRR abs/1703.10293 (2017) - [i9]Greg Bodwin:
Testing Core Membership in Public Goods Economies. CoRR abs/1705.01570 (2017) - [i8]Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams:
Optimal Vertex Fault Tolerant Spanners (for fixed stretch). CoRR abs/1710.03164 (2017) - [i7]Amir Abboud, Greg Bodwin:
Reachability Preservers: New Extremal Bounds and Approximation Algorithms. CoRR abs/1710.11250 (2017) - 2016
- [c6]Greg Bodwin, Sebastian Krinninger:
Fully Dynamic Spanners with Worst-Case Update Time. ESA 2016: 17:1-17:18 - [c5]Amir Abboud, Greg Bodwin:
Error Amplification for Pairwise Spanner Lower Bounds. SODA 2016: 841-854 - [c4]Greg Bodwin, Virginia Vassilevska Williams:
Better Distance Preservers and Additive Spanners. SODA 2016: 855-872 - [c3]Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, Morten Stöckel:
Graph Reconstruction with a Betweenness Oracle. STACS 2016: 5:1-5:14 - [c2]Amir Abboud, Greg Bodwin:
The 4/3 additive spanner exponent is tight. STOC 2016: 351-361 - [i6]Greg Bodwin:
Linear Size Distance Preservers. CoRR abs/1605.01106 (2016) - [i5]Greg Bodwin, Sebastian Krinninger:
Fully Dynamic Spanners with Worst-Case Update Time. CoRR abs/1606.07864 (2016) - [i4]Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. CoRR abs/1607.07497 (2016) - 2015
- [c1]Gregory Bodwin, Virginia Vassilevska Williams:
Very Sparse Additive Spanners and Emulators. ITCS 2015: 377-382 - [i3]Gregory Bodwin, Virginia Vassilevska Williams:
Better Distance Preservers and Additive Spanners. CoRR abs/1505.05599 (2015) - [i2]Gregory Bodwin, Virginia Vassilevska Williams:
Very Sparse Additive Spanners and Emulators. CoRR abs/1505.05630 (2015) - [i1]Amir Abboud, Greg Bodwin:
The 4/3 Additive Spanner Exponent is Tight. CoRR abs/1511.00700 (2015)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-01 01:15 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
