research
∙
07/28/2023
Dynamic algorithms for k-center on graphs
In this paper we give the first efficient algorithms for the k-center pr...
share
research
∙
07/19/2023
On Dynamic Graph Algorithms with Predictions
We study dynamic algorithms in the model of algorithms with predictions....
research
∙
07/18/2023
Fast 2-Approximate All-Pairs Shortest Paths
In this paper, we revisit the classic approximate All-Pairs Shortest Pat...
research
∙
07/17/2023
Fast Algorithms for Energy Games in Special Cases
In this paper, we study algorithms for special cases of energy games, a ...
research
∙
03/10/2023
Bootstrapping Dynamic Distance Oracles
Designing approximate all-pairs distance oracles in the fully dynamic se...
research
∙
11/08/2022
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
We provide the first deterministic data structure that given a weighted ...
research
∙
11/02/2022
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
We provide new tradeoffs between approximation and running time for the ...
research
∙
05/24/2022
The Laplacian Paradigm in the Broadcast Congested Clique
In this paper, we bring the main tools of the Laplacian paradigm to the ...
research
∙
12/06/2021
Faster Cut Sparsification of Weighted Graphs
A cut sparsifier is a reweighted subgraph that maintains the weights of ...
research
∙
11/17/2021
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions
Spanners have been shown to be a powerful tool in graph algorithms. Many...
research
∙
11/05/2021
Fast Deterministic Fully Dynamic Distance Approximation
In this paper, we develop deterministic fully dynamic algorithms for com...
research
∙
12/31/2020
Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
research
∙
04/21/2020
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
We give the first non-trivial fully dynamic probabilistic tree embedding...
research
∙
04/21/2020
Dynamic Maintanance of Low-Stretch Probabilistic Tree Embeddings with Applications
We give the first non-trivial fully dynamic probabilistic tree embedding...
research
∙
10/31/2019
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Consider the following "local" cut-detection problem in a directed graph...
research
∙
04/17/2019
A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems
Consider the following "local" cut-detection problem in a directed graph...
research
∙
10/25/2018
