Gregory Bodwin

SIAM J. Comput., 2024

Additive Spanner Lower Bounds with Optimal Inner Graph Structure.

[BibT_eX]

[DOI]

Nicole Wein

Zixuan Xu

CoRR, 2024

The Discrepancy of Shortest Paths.

[BibT_eX]

[DOI]

CoRR, 2024

An Alternate Proof of Near-Optimal Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

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

[BibT_eX]

[DOI]

Bernhard Haeupler

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

Spanning Adjacency Oracles in Sublinear Time.

[BibT_eX]

[DOI]

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?

[BibT_eX]

[DOI]

Aaron Bernstein

Nicole Wein

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

2023

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs.

[BibT_eX]

[DOI]

J. ACM, October, 2023

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

[BibT_eX]

[DOI]

Lily Wang

CoRR, 2023

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

[BibT_eX]

[DOI]

Forest Zhang

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

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

[BibT_eX]

[DOI]

Yasamin Nazari

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

Bridge Girth: A Unifying Notion in Network Design.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

2022

A unified view of graph regularity via matrix decompositions.

[BibT_eX]

[DOI]

Santosh S. Vempala

Random Struct. Algorithms, 2022

A note on distance-preserving graph sparsification.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2022

Partially Optimal Edge Fault-Tolerant Spanners.

[BibT_eX]

[DOI]

Caleb Robelle

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

Vertex Fault-Tolerant Emulators.

[BibT_eX]

[DOI]

Yasamin Nazari

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

New Additive Spanner Lower Bounds by an Unlayered Obstacle Product.

[BibT_eX]

[DOI]

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

2021

Better Distance Preservers and Additive Spanners.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

New Results on Linear Size Distance Preservers.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Weighted Sparse and Lightweight Spanners with Local Additive Error.

[BibT_eX]

[DOI]

CoRR, 2021

On Additive Spanners in Weighted Graphs with Local Error.

[BibT_eX]

[DOI]

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

Multi-Level Weighted Additive Spanners.

[BibT_eX]

[DOI]

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

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time.

[BibT_eX]

[DOI]

Mohammad Javad Latifi Jebelli

Caleb Robelle

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

2020

Graph spanners: A tutorial review.

[BibT_eX]

[DOI]

Stephen G. Kobourov

Richard Spence

Comput. Sci. Rev., 2020

Some General Structure for Extremal Sparsification Problems.

[BibT_eX]

[DOI]

CoRR, 2020

Weighted Additive Spanners.

[BibT_eX]

[DOI]

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

New Fault Tolerant Subset Preservers.

[BibT_eX]

[DOI]

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

2019

Strategy-Stealing is Non-Constructive.

[BibT_eX]

[DOI]

Ofer Grossman

Electron. Colloquium Comput. Complex., 2019

Matrix Decompositions and Sparse Graph Regularity.

[BibT_eX]

[DOI]

Santosh S. Vempala

CoRR, 2019

On the Structure of Unique Shortest Paths in Graphs.

[BibT_eX]

[DOI]

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

A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners.

[BibT_eX]

[DOI]

Shyamal Patel

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

2018

Sketching distances in graphs.

[BibT_eX]

[DOI]

Gregory Michael Bodwin

PhD thesis, 2018

A Hierarchy of Lower Bounds for Sublinear Additive Spanners.

[BibT_eX]

[DOI]

Seth Pettie

SIAM J. Comput., 2018

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

[BibT_eX]

[DOI]

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

2017

The 4/3 Additive Spanner Exponent Is Tight.

[BibT_eX]

[DOI]

J. ACM, 2017

Linear Size Distance Preservers.

[BibT_eX]

[DOI]

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

Preserving Distances in Very Faulty Graphs.

[BibT_eX]

[DOI]

Fabrizio Grandoni

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

Testing Core Membership in Public Goods Economies.

[BibT_eX]

[DOI]

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

2016

Graph Reconstruction with a Betweenness Oracle.

[BibT_eX]

[DOI]

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

Error Amplification for Pairwise Spanner Lower Bounds.

[BibT_eX]

[DOI]

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

Fully Dynamic Spanners with Worst-Case Update Time.

[BibT_eX]

[DOI]

Sebastian Krinninger

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

2015

Very Sparse Additive Spanners and Emulators.

[BibT_eX]

[DOI]

Gregory Bodwin