research
∙
09/14/2023
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan,...
share
research
∙
09/13/2023
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
We study a new and stronger notion of fault-tolerant graph structures wh...
research
∙
08/26/2023
Spanning Adjacency Oracles in Sublinear Time
Suppose we are given an n-node, m-edge input graph G, and the goal is to...
research
∙
08/24/2023
Are there graphs whose shortest path structure requires large edge weights?
The aspect ratio of a weighted graph G is the ratio of its maximum edge ...
research
∙
05/29/2023
An Alternate Proof of Near-Optimal Light Spanners
In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] es...
research
∙
04/05/2023
Folklore Sampling is Optimal for Exact Hopsets: Confirming the √(n) Barrier
For a graph G, a D-diameter-reducing exact hopset is a small set of addi...
research
∙
12/22/2022
Bridge Girth: A Unifying Notion in Network Design
A classic 1993 paper by Althőfer et al. proved a tight reduction from sp...
research
∙
09/08/2022
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
In competitive games, it is common to assign each player a real number r...
research
∙
09/08/2022
Epic Fail: Emulators can tolerate polynomially many edge faults for free
A t-emulator of a graph G is a graph H that approximates its pairwise sh...
research
∙
07/24/2022
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
For an input graph G, an additive spanner is a sparse subgraph H whose s...
research
∙
09/16/2021
Vertex Fault-Tolerant Emulators
A k-spanner of a graph G is a sparse subgraph that preserves its shortes...
research
∙
03/17/2021
On additive spanners in weighted graphs with local error
An additive +β spanner of a graph G is a subgraph which preserves distan...
research
∙
02/22/2021
Partially Optimal Edge Fault-Tolerant Spanners
Recent work has established that, for every positive integer k, every n-...
research
∙
02/19/2021
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt ...
research
∙
02/11/2021
Multi-level Weighted Additive Spanners
Given a graph G = (V,E), a subgraph H is an additive +β spanner if _H(u,...
research
∙
07/16/2020
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Recent work has pinned down the existentially optimal size bounds for ve...
research
∙
02/15/2020
Weighted Additive Spanners
An α-additive spanner of an undirected graph G=(V, E) is a subgraph H su...
research
∙
01/21/2020
Some General Structure for Extremal Sparsification Problems
This paper is about a branch of theoretical computer science that studie...
research
∙
11/26/2019
Matrix Decompositions and Sparse Graph Regularity
We introduce and study a matrix decomposition that is a common generaliz...
research
∙
11/15/2019
Strategy-Stealing is Non-Constructive
In many combinatorial games, one can prove that the first player wins un...
research
∙
09/07/2019
Graph Spanners: A Tutorial Review
This tutorial review provides a guiding reference to researchers who wan...
research
∙
12/14/2018
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
We give a short and easy upper bound on the worst-case size of fault tol...
research
∙
04/25/2018
On the Structure of Unique Shortest Paths in Graphs
This paper develops a structural theory of unique shortest paths in real...
research
∙
10/30/2017