research
∙
07/13/2023
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
In this paper, we study parallel algorithms for the correlation clusteri...
share
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
∙
12/29/2022
(1-ε)-Approximate Maximum Weighted Matching in poly(1/ε, log n) Time in the Distributed and Parallel Settings
The maximum weighted matching (MWM) problem is one of the most well-stud...
research
∙
05/17/2022
Narrowing the LOCALx2013CONGEST Gaps in Sparse Networks via Expander Decompositions
Many combinatorial optimization problems can be approximated within (1 ±...
research
∙
11/02/2021
Adaptive Massively Parallel Constant-round Tree Contraction
Miller and Reif's FOCS'85 classic and fundamental tree contraction algor...
research
∙
09/22/2020
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
Given a graph G=(V,E) with arboricity α, we study the problem of decompo...
research
∙
06/30/2020
Lower Bounds for Dynamic Distributed Task Allocation
We study the problem of distributed task allocation in multi-agent syste...
research
∙
08/01/2019
Distributed Data Summarization in Well-Connected Networks
We study distributed algorithms for some fundamental problems in data su...
research
∙
07/29/2019
Distributed Dense Subgraph Detection and Low Outdegree Orientation
The maximum density subgraph problem, introduced in the 80s by Picard an...
research
∙
01/02/2019
Towards the Locality of Vizing's Theorem
Vizing showed that it suffices to color the edges of a simple graph usin...
research
∙
11/25/2017