research
∙
07/25/2023
Fully Dynamic Consistent k-Center Clustering
We study the consistent k-center clustering problem. In this problem, th...
share
research
∙
07/25/2023
Noisy k-means++ Revisited
The k-means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a cla...
research
∙
10/28/2022
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
We introduce stronger notions for approximate single-source shortest-pat...
research
∙
10/21/2022
A Simple Deterministic Distributed Low-Diameter Clustering
We give a simple, local process for nodes in an undirected graph to form...
research
∙
09/23/2022
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
This paper presents significantly improved deterministic algorithms for ...
research
∙
09/23/2022
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
We develop a general deterministic distributed method for locally roundi...
research
∙
07/16/2022
A Nearly Tight Analysis of Greedy k-means++
The famous k-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] i...
research
∙
04/29/2022
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
This paper presents efficient distributed algorithms for a number of fun...
research
∙
04/20/2022
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees
We study complexity classes of local problems on regular trees from the ...
research
∙
04/18/2022
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
This paper presents new deterministic and distributed low-diameter decom...
research
∙
04/12/2022
Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel Distributed Algorithms
This paper presents near-optimal deterministic parallel and distributed ...
research
∙
02/09/2022
The Landscape of Distributed Complexities on Trees and Beyond
We study the local complexity landscape of locally checkable labeling (L...
research
∙
11/05/2021
On Homomorphism Graphs
We introduce a new type of examples of bounded degree acyclic Borel grap...
research
∙
06/03/2021
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
research
∙
03/30/2021
The randomized local computation complexity of the Lovász local lemma
The Local Computation Algorithm (LCA) model is a popular model in the fi...
research
∙
03/25/2021
Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
We classify which local problems with inputs on oriented paths have so-c...
research
∙
03/15/2021
Of Toasts and Tails
We present an intimate connection among the following fields: (a) dist...
research
∙
07/16/2020
Improved Deterministic Network Decomposition
Network decomposition is a central tool in distributed graph algorithms....
research
∙
07/02/2020
Adapting k-means algorithms for outliers
This paper shows how to adapt several simple and classical sampling-base...
research
∙
06/08/2020
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted ...
research
∙
03/05/2020
Simple and sharp analysis of k-means||
We present a truly simple analysis of k-means|| (Bahmani et al., PVLDB 2...
research
∙
02/18/2020
k-means++: few more steps yield constant approximation
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a sta...
research
∙
07/25/2019