
StrongDiameter Network Decomposition
Network decomposition is a central concept in the study of distributed g...
read it

HopConstrained Oblivious Routing
We prove the existence of an oblivious routing scheme that is poly(log n...
read it

Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
We present a simple deterministic distributed algorithm that computes a ...
read it

LowCongestion Shortcuts for Graphs Excluding Dense Minors
We prove that any nnode graph G with diameter D admits shortcuts with c...
read it

Improved Deterministic Network Decomposition
Network decomposition is a central tool in distributed graph algorithms....
read it

A Massively Parallel Algorithm for Minimum Weight Vertex Cover
We present a massively parallel algorithm, with nearlinear memory per m...
read it

Massively Parallel Algorithms for Distance Approximation and Spanners
Over the past decade, there has been increasing interest in distributed/...
read it

Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
We present O(loglog n) round scalable Massively Parallel Computation alg...
read it

Faster Algorithms for Edge Connectivity via Random 2Out Contractions
We provide a simple new randomized contraction approach to the global mi...
read it

Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond
Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and P...
read it

PolylogarithmicTime Deterministic Network Decomposition and Distributed Derandomization
We present a simple polylogarithmictime deterministic distributed algor...
read it

On the Use of Randomness in Local Distributed Graph Algorithms
We attempt to better understand randomization in local distributed graph...
read it

On the Complexity of Distributed Splitting Problems
One of the fundamental open problems in the area of distributed graph al...
read it

Improved Distributed Approximations for MinimumWeight TwoEdgeConnected Spanning Subgraph
The minimumweight 2edgeconnected spanning subgraph (2ECSS) problem i...
read it

Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation
We present a very simple randomized partitioning procedure for graph col...
read it

Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
We introduce a method for sparsifying distributed algorithms and exhibit...
read it

Distributed Computation in the NodeCongested Clique
The Congested Clique model of distributed computing, which was introduce...
read it

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
We show that many classical optimization problems  such as (1±ϵ)appr...
read it

Improved Distributed ΔColoring
We present a randomized distributed algorithm that computes a Δcoloring...
read it

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
We present O( n)round algorithms in the Massively Parallel Computation ...
read it

A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Sampling constitutes an important tool in a variety of areas: from machi...
read it

Improved Distributed Algorithms for Exact Shortest Paths
Computing shortest paths is one of the central problems in the theory of...
read it

Deterministic Distributed EdgeColoring with Fewer Colors
We present a deterministic distributed algorithm, in the LOCAL model, th...
read it

On Derandomizing Local Distributed Algorithms
The gap between the known randomized and deterministic local distributed...
read it
Mohsen Ghaffari
is this you? claim profile