# Mohsen Ghaffari

## Contact Details

NameMohsen Ghaffari |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Data Structures and Algorithms (20) Computer Science - Distributed; Parallel; and Cluster Computing (13) Mathematics - Combinatorics (3) Mathematics - Information Theory (2) Computer Science - Information Theory (2) Computer Science - Networking and Internet Architecture (1) Computer Science - Discrete Mathematics (1) |

## Publications Authored By Mohsen Ghaffari

We present a deterministic distributed algorithm that computes a $(2\Delta-1)$-edge-coloring, or even list-edge-coloring, in any $n$-node graph with maximum degree $\Delta$, in $O(\log^7 \Delta \log n)$ rounds. This answers one of the long-standing open questions of \emph{distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e. Read More

We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows: -- An $O(\log^2 \Delta \log n)$-round deterministic distributed algorithm for computing a maximal matching, in $n$-node graphs with maximum degree $\Delta$. Read More

In a recent breakthrough, Paz and Schwartzman [SODA'17] presented a single-pass ($2+\epsilon$)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses $O(n\log^2 n)$ bits of space, for any constant $\epsilon>0$. In this note, we present a different analysis, for essentially the same algorithm, that improves the space complexity to the optimal bound of $O(n\log n)$ bits, while also providing a more intuitive explanation of the process. Read More

This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and $(\Delta+1)$-vertex coloring), the randomized complexity is at most polylogarithmic in the size $n$ of the network, while the best deterministic complexity is typically $2^{O(\sqrt{\log n})}$. Understanding and narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. Read More

We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: -- We present a $poly(\log n)$ round deterministic algorithm for $(2\Delta-1)\cdot (1+o(1))$-edge-coloring, where $\Delta$ denotes the maximum degree. Modulo the $1+o(1)$ factor, this settles one of the long-standing open problems of the area from the 1990's (see e. Read More

In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Read More

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+ \sqrt{n})$ round complexity lower bound. Read More

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some recent techniques, also leads to a near-optimal global complexity. Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after $O(\log n)$ rounds. Read More

We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony must relocate to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. Read More

All consensus hierarchies in the literature assume that we have, in addition to copies of a given object, an unbounded number of registers. But why do we really need these registers? This paper considers what would happen if one attempts to solve consensus using various objects but without any registers. We show that under a reasonable assumption, objects like queues and stacks cannot emulate the missing registers. Read More

We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention. We begin by studying upper and lower bounds for this problem in a {\em standard abstract MAC layer model}---identifying an interesting dependence between the structure of unreliable links and achievable time complexity. Read More

This paper presents a near-optimal distributed approximation algorithm for the minimum-weight connected dominating set (MCDS) problem. The presented algorithm finds an $O(\log n)$ approximation in $\tilde{O}(D+\sqrt{n})$ rounds, where $D$ is the network diameter and $n$ is the number of nodes. MCDS is a classical NP-hard problem and the achieved approximation factor $O(\log n)$ is known to be optimal up to a constant factor, unless P=NP. Read More

We introduce collision free layerings as a powerful way to structure radio networks. These layerings can replace hard-to-compute BFS-trees in many contexts while having an efficient randomized distributed construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multi-message communication primitives. Read More

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter $D$. It improves over the currently best known $O(D\log\frac{n}{D}\,+\,\log^2 n)$ algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. Read More

We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any $n$-round interactive protocol using $N$ rounds over an adversarial channel that corrupts up to $\rho N$ transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate $\rho$, communication complexity $N$, and computational complexity. Read More

We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings. Most significantly, we explore adaptive interactive communication where the communicating parties decide who should speak next based on the history of the interaction. Braverman and Rao [STOC'11] show that non-adaptively one can code for any constant error rate below 1/4 but not more. Read More

We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their primary applications, these decompositions allow us to achieve information flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: (I) A decomposition of each undirected graph with vertex-connectivity $k$ into (fractionally) vertex-disjoint weighted dominating trees with total weight $\Omega(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds. Read More

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, $O(\log n)$ bits can be transmitted over each edge (a.k. Read More

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity, our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are edge-disjoint spanning trees. Read More

We consider the well-studied radio network model: a synchronous model with a graph G=(V,E) with |V|=n where in each round, each node either transmits a packet, with length B=Omega(log n) bits, or listens. Each node receives a packet iff it is listening and exactly one of its neighbors is transmitting. We consider the problem of k-message broadcast, where k messages, each with Theta(B) bits, are placed in an arbitrary nodes of the graph and the goal is to deliver all messages to all the nodes. Read More

We present distributed randomized leader election protocols for multi-hop radio networks that elect a leader in almost the same time $T_{BC}$ required for broadcasting a message. For the setting without collision detection, our algorithm runs with high probability in $O(D \log \frac{n}{D} + \log^3 n) \min\{\log\log n,\log \frac{n}{D}\}$ rounds on any $n$-node network with diameter $D$. Since $T_{BC} = \Theta(D \log \frac{n}{D} + \log^2 n)$ is a lower bound, our upper bound is optimal up to a factor of at most $\log \log n$ and the extra $\log n$ factor on the additive term. Read More

The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight bounds for this problem in two well-studied wireless network models: the classical model, in which links are reliable and collisions consistent, and the more recent dual graph model, which introduces unreliable edges. Our results prove that the Decay strategy, commonly used for local broadcast in the classical setting, is optimal. Read More

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. Read More