research
∙
08/01/2023
Conditionally Optimal Parallel Coloring of Forests
We show the first conditionally optimal deterministic algorithm for 3-co...
share
research
∙
07/25/2023
Fully Dynamic Consistent k-Center Clustering
We study the consistent k-center clustering problem. In this problem, th...
research
∙
07/25/2023
Noisy k-means++ Revisited
The k-means++ algorithm by Arthur and Vassilvitskii [SODA 2007] is a cla...
research
∙
04/19/2023
Nearly Work-Efficient Parallel DFS in Undirected Graphs
We present the first parallel depth-first search algorithm for undirecte...
research
∙
03/28/2023
Faster Deterministic Distributed MIS and Approximate Matching
We present an Õ(log^2 n) round deterministic distributed algorithm for t...
research
∙
03/01/2023
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights
This paper presents parallel and distributed algorithms for single-sourc...
research
∙
01/26/2023
Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
We consider the problem of designing deterministic graph algorithms for ...
research
∙
11/14/2022
Massively Parallel Algorithms for b-Matching
This paper presents an O(loglogd̅) round massively parallel algorithm fo...
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
∙
06/03/2022
Improved Deterministic Connectivity in Massively Parallel Computation
A long line of research about connectivity in the Massively Parallel Com...
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
∙
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
∙
02/22/2020
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
We present O(loglog n) round scalable Massively Parallel Computation alg...
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
∙
10/30/2019