research
∙
05/23/2022
Distributed Computations in Fully-Defective Networks
We address fully-defective asynchronous networks, in which all links are...
share
research
∙
05/18/2022
Deterministic Near-Optimal Distributed Listing of Cliques
The importance of classifying connections in large graphs has been the m...
research
∙
03/13/2022
Distributed Subgraph Finding: Progress and Challenges
This is a survey of the exciting recent progress made in understanding t...
research
∙
01/09/2022
Quantum Distributed Algorithms for Detection of Cliques
The possibilities offered by quantum computing have drawn attention in t...
research
∙
09/14/2021
Distributed Vertex Cover Reconfiguration
Reconfiguration schedules, i.e., sequences that gradually transform one ...
research
∙
05/13/2021
On Sparsity Awareness in Distributed Computations
We extract a core principle underlying seemingly different fundamental d...
research
∙
05/12/2021
Locally Checkable Labelings with Small Messages
A rich line of work has been addressing the computational complexity of ...
research
∙
05/03/2021
Fault Tolerant Max-Cut
In this work, we initiate the study of fault tolerant Max Cut, where giv...
research
∙
02/14/2021
Near-Optimal Scheduling in the Congested Clique
This paper provides three nearly-optimal algorithms for scheduling t job...
research
∙
01/19/2021
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
In this paper we give fast distributed graph algorithms for detecting an...
research
∙
11/14/2020
Tight Distributed Listing of Cliques
Much progress has recently been made in understanding the complexity lan...
research
∙
11/10/2020
Distributed Distance Approximation
Diameter, radius and eccentricities are fundamental graph parameters, wh...
research
∙
10/26/2020
Distance Computations in the Hybrid Network Model via Oracle Simulations
The Hybrid network model was introduced in [Augustine et al., SODA '20] ...
research
∙
09/17/2020
Finding Subgraphs in Highly Dynamic Networks
In this paper we consider the fundamental problem of finding subgraphs i...
research
∙
07/10/2020
On Distributed Listing of Cliques
We show an Õ(n^p/(p+2))-round algorithm in the model for listing of K_p ...
research
∙
06/06/2020
Distributed Approximation on Power Graphs
We investigate graph problems in the following setting: we are given a g...
research
∙
05/24/2019
Hardness of Distributed Optimization
This paper studies lower bounds for fundamental optimization problems in...
research
∙
04/25/2019
Distributed Detection of Cliques in Dynamic Networks
This paper provides an in-depth study of the fundamental problems of fin...
research
∙
03/14/2019
Fast Approximate Shortest Paths in the Congested Clique
We design fast deterministic algorithms for distance computation in the ...
research
∙
01/13/2019
Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
This paper provides a surprisingly simple method for obtaining fast (con...
research
∙
01/07/2019
Smaller Cuts, Higher Lower Bounds
This paper proves strong lower bounds for distributed computing in the C...
research
∙
11/05/2018
The Sparsest Additive Spanner via Multiple Weighted BFS Trees
Spanners are fundamental graph structures that sparsify graphs at the co...
research
∙
10/04/2018
Distributed Reconfiguration of Maximal Independent Sets
Consider the following problem: given a graph and two maximal independen...
research
∙
05/10/2018
Erasure Correction for Noisy Radio Networks
The radio network model is a well-studied abstraction for modeling wirel...
research
∙
02/13/2018
Sparse Matrix Multiplication with Bandwidth Restricted All-to-All Communication
We show how to multiply two n × n matrices over semirings in the Congest...
research
∙
02/09/2018
Distributed Spanner Approximation
We address the fundamental network design problem of constructing approx...
research
∙
11/09/2017
Fast Distributed Approximation for TAP and 2-Edge-Connectivity
The tree augmentation problem (TAP) is a fundamental network design prob...
research
∙
11/05/2017