We present randomized distributed algorithms for the maximal independent...
We provide the first deterministic distributed synchronizer with near-op...
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the no...
We present an O(log^3log n)-round distributed algorithm for the
(Δ+1)-co...
We present the first parallel depth-first search algorithm for undirecte...
We present an Õ(log^2 n)
round deterministic distributed algorithm for t...
Is fully decentralized graph streaming possible? We consider this questi...
This paper provides a cut-strategy that produces constant-hop expanders ...
This paper presents an O(loglogd̅) round massively parallel
algorithm fo...
The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is ...
We present a randomized Local Computation Algorithm (LCA) with query
com...
This paper presents significantly improved deterministic algorithms for ...
We develop a general deterministic distributed method for locally roundi...
The node-averaged complexity of a distributed algorithm running on a gra...
We describe a simple deterministic O( ε^-1logΔ) round
distributed algori...
We present a universally-optimal distributed algorithm for the exact wei...
This paper presents efficient distributed algorithms for a number of
fun...
Network decomposition is a central concept in the study of distributed g...
We prove the existence of an oblivious routing scheme that is
poly(log n...
We present a simple deterministic distributed algorithm that computes a
...
We prove that any n-node graph G with diameter D admits shortcuts with
c...
Network decomposition is a central tool in distributed graph algorithms....
We present a massively parallel algorithm, with near-linear memory per
m...
Over the past decade, there has been increasing interest in
distributed/...
We present O(loglog n) round scalable Massively Parallel Computation
alg...
We provide a simple new randomized contraction approach to the global mi...
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and
P...
We present a simple polylogarithmic-time deterministic distributed algor...
We attempt to better understand randomization in local distributed graph...
One of the fundamental open problems in the area of distributed graph
al...
The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem i...
We present a very simple randomized partitioning procedure for graph
col...
We introduce a method for sparsifying distributed algorithms and exhibit...
The Congested Clique model of distributed computing, which was introduce...
We show that many classical optimization problems --- such as
(1±ϵ)-appr...
We present a randomized distributed algorithm that computes a
Δ-coloring...
We present O( n)-round algorithms in the Massively Parallel
Computation ...
Sampling constitutes an important tool in a variety of areas: from
machi...
Computing shortest paths is one of the central problems in the theory of...
We present a deterministic distributed algorithm, in the LOCAL model, th...
The gap between the known randomized and deterministic local distributed...