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
∙
03/10/2023
Bootstrapping Dynamic Distance Oracles
Designing approximate all-pairs distance oracles in the fully dynamic se...
research
∙
03/04/2023
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Oblivious routing is a well-studied distributed paradigm that uses stati...
research
∙
02/12/2023
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple n-vertex, m-edge graph G undergoing edge insertions and d...
research
∙
11/17/2022
Incremental Approximate Maximum Flow in m^1/2+o(1) update time
We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flo...
research
∙
05/03/2022
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
We present a nearly-linear time algorithm for finding a minimum-cost flo...
research
∙
10/29/2021
Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
We provide universally-optimal distributed graph algorithms for (1+ε)-ap...
research
∙
06/07/2021
Local Algorithms for Estimating Effective Resistance
Effective resistance is an important metric that measures the similarity...
research
∙
12/31/2020
Minor Sparsifiers and the Distributed Laplacian Paradigm
We study distributed algorithms built around edge contraction based vert...
research
∙
07/06/2020
Faster Graph Embeddings via Coarsening
Graph embeddings are a ubiquitous tool for machine learning tasks, such ...
research
∙
05/05/2020
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
We introduce a notion for hierarchical graph clustering which we call th...
research
∙
05/05/2020
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
We present a general framework of designing efficient dynamic approximat...
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
∙
09/14/2019
A Tree Structure For Dynamic Facility Location
We study the metric facility location problem with client insertions and...
research
∙
09/13/2019
Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
Graphs naturally appear in several real-world contexts including social ...
research
∙
08/11/2019
Fully Dynamic k-Center Clustering in Doubling Metrics
In the k-center clustering problem, we are given a set of n points in a ...
research
∙
06/24/2019
Fully Dynamic Spectral Vertex Sparsifiers and Applications
We study dynamic algorithms for maintaining spectral vertex sparsifiers ...
research
∙
04/13/2018
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Spanning trees of low average stretch on the non-tree edges, as introduc...
research
∙
04/11/2018
Fully Dynamic Effective Resistances
In this paper we consider the fully-dynamic All-Pairs Effective Resistan...
research
∙
02/26/2018
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
We consider the problem of dynamically maintaining (approximate) all-pai...
research
∙
12/18/2017