research
∙
08/08/2023
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Over the past decade, a long line of research has investigated the distr...
share
research
∙
07/18/2023
No distributed quantum advantage for approximate graph coloring
We give an almost complete characterization of the hardness of c-colorin...
research
∙
06/01/2023
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
In this work, we present a constant-round algorithm for the 2-ruling set...
research
∙
04/19/2023
Coloring Fast with Broadcasts
We present an O(log^3log n)-round distributed algorithm for the (Δ+1)-co...
research
∙
04/19/2023
List Defective Colorings: Distributed Algorithms and Applications
The distributed coloring problem is at the core of the area of distribut...
research
∙
01/16/2023
A Distributed Palette Sparsification Theorem
Is fully decentralized graph streaming possible? We consider this questi...
research
∙
11/03/2022
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
We investigate the distributed complexity of maximal matching and maxima...
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
∙
08/17/2022
Node and Edge Averaged Complexities of Local Graph Problems
The node-averaged complexity of a distributed algorithm running on a gra...
research
∙
07/24/2022
Contention Resolution for Coded Radio Networks
Randomized backoff protocols, such as exponential backoff, are a powerfu...
research
∙
06/02/2022
Distributed Edge Coloring in Time Polylogarithmic in Δ
We provide new deterministic algorithms for the edge coloring problem, w...
research
∙
02/16/2022
Near-Shortest Path Routing in Hybrid Communication Networks
Hybrid networks, i.e., networks that leverage different means of communi...
research
∙
02/14/2022
Routing Schemes and Distance Oracles in the Hybrid Model
The 𝖧𝖸𝖡𝖱𝖨𝖣 model was introduced as a means for theoretical study of dist...
research
∙
12/08/2021
Improved Distributed Fractional Coloring Algorithms
We prove new bounds on the distributed fractional coloring problem in th...
research
∙
12/01/2021
Near-Optimal Distributed Degree+1 Coloring
We present a new approach to randomized distributed graph coloring that ...
research
∙
11/20/2021
Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings
We provide CONGEST model algorithms for approximating minimum weighted v...
research
∙
10/01/2021
Distributed Δ-Coloring Plays Hide-and-Seek
We prove several new tight distributed lower bounds for classic symmetry...
research
∙
06/04/2021
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log...
research
∙
12/28/2020
Efficient Randomized Distributed Coloring in CONGEST
Distributed vertex coloring is one of the classic problems and probably ...
research
∙
11/19/2020
Approximate Bipartite Vertex Cover in the CONGEST Model
We give efficient distributed algorithms for the minimum vertex cover pr...
research
∙
11/09/2020
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
We present a simple deterministic distributed algorithm that computes a ...
research
∙
08/10/2020
Coloring Fast Without Learning Your Neighbors' Colors
We give an improved randomized CONGEST algorithm for distance-2 coloring...
research
∙
06/15/2020
Computing Shortest Paths and Diameter in the Hybrid Network Model
The 𝖧𝖸𝖡𝖱𝖨𝖣 model, introduced in [Augustine et al., SODA '20], provides a...
research
∙
05/13/2020
Distance-2 Coloring in the CONGEST Model
We give efficient randomized and deterministic distributed algorithms fo...
research
∙
02/25/2020
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
The problem of coloring the edges of an n-node graph of maximum degree Δ...
research
∙
02/18/2020
Distributed Maximum Matching Verification in CONGEST
We study the maximum cardinality matching problem in a standard distribu...
research
∙
12/05/2019
Efficient Deterministic Distributed Coloring with Small Bandwidth
We show that the (degree+1)-list coloring problem can be solved determin...
research
∙
09/04/2019
Shortest Paths in a Hybrid Network Model
We introduce a communication model for hybrid networks, where nodes have...
research
∙
07/08/2019
Faster Deterministic Distributed Coloring Through Recursive List Coloring
We provide novel deterministic distributed vertex coloring algorithms. A...
research
∙
06/02/2019
On the Use of Randomness in Local Distributed Graph Algorithms
We attempt to better understand randomization in local distributed graph...
research
∙
05/28/2019
On the Complexity of Distributed Splitting Problems
One of the fundamental open problems in the area of distributed graph al...
research
∙
05/26/2019
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
We develop deterministic approximation algorithms for the minimum domina...
research
∙
02/24/2019
Latency, Capacity, and Distributed MST
Consider the problem of building a minimum-weight spanning tree for a gi...
research
∙
02/20/2019
Competitive Concurrent Distributed Scheduling
We introduce a new scheduling problem in distributed computing that we c...
research
∙
09/18/2018
Optimal strategies for patrolling fences
A classical multi-agent fence patrolling problem asks: What is the maxim...
research
∙
06/26/2018
The Communication Cost of Information Spreading in Dynamic Networks
This paper investigates the message complexity of distributed informatio...
research
∙
05/18/2018
Distributed Computation in the Node-Congested Clique
The Congested Clique model of distributed computing, which was introduce...
research
∙
05/18/2018
Deterministic Distributed Ruling Sets of Line Graphs
An (α,β)-ruling set of a graph G=(V,E) is a set R⊆ V such that for any n...
research
∙
05/09/2018
Efficient Distributed Computation of MIS and Generalized MIS in Linear Hypergraphs
Given a graph, a maximal independent set (MIS) is a maximal subset of pa...
research
∙
03/08/2018
Improved Distributed Δ-Coloring
We present a randomized distributed algorithm that computes a Δ-coloring...
research
∙
02/27/2018
Local Distributed Algorithms in Highly Dynamic Networks
The present paper studies local distributed graph problems in highly dyn...
research
∙
11/15/2017
Deterministic Distributed Edge-Coloring with Fewer Colors
We present a deterministic distributed algorithm, in the LOCAL model, th...
research
∙
11/06/2017