Publications

We study rectangular matrix multiplication in the low-bandwidth model of distributed computing. There are $n$ computers; initially the input matrices are distributed evenly between computers, and in each communication round every computer can send and receive an $O(\log n)$-bit message. Eventually each computer must output its designated part of the product matrix.

While prior work has focused primarily on square $n\times n$ multiplication under various sparsity assumptions, we study rectangular instances with no sparsity assumption. We denote by $⟨a,b,c⟩$ the task of multiplying an $a\times b$ matrix by a $b\times c$ matrix in this model. We concentrate on two natural aspect ratios, $⟨n,d,n⟩$ and $⟨d,n,d⟩$, for $d\le n$, and we study how the round complexity depends on $n$ and $d$.

When $d\to n$, both $⟨n,d,n⟩$ and $⟨d,n,d⟩$ approach $⟨n,n,n⟩$, which is the usual task of multiplying square matrices. If we consider multiplication over semirings, the current best upper bound in that case is $O(n^{4/3})$ rounds, and there is a trivial unconditional lower bound of $\Omega (n)$.

We show that for $⟨d,n,d⟩$, we can achieve the complexity of $\tilde{O}(d^{4/3})$, which seems like a natural generalization of the upper bound $\tilde{O}(n^{4/3})$ when $d=n$. However, the case of $⟨n,d,n⟩$ is fundamentally different, and also exhibits a phase transition. We show that for $d\le \sqrt{n}$, the complexity of $⟨n,d,n⟩$ is $\Theta (d\sqrt{n})$; we have matching upper and lower bounds. However, the behavior is genuinely different in the region $d\ge \sqrt{n}$, where the upper bound is $O(d^{2/3}{n}^{2/3})$.

In prior work, Gupta et al. (SPAA 2022) presented a distributed algorithm for multiplying sparse $n\times n$ matrices, using $n$ computers. They assumed that the input matrices are uniformly sparse—there are at most $d$ non-zeros in each row and column—and the task is to compute a uniformly sparse part of the product matrix. The sparsity structure is globally known in advance (this is the supported setting).

As input, each computer receives one row of each input matrix, and each computer needs to output one row of the product matrix. In each communication round each computer can send and receive one $O(\log n)$-bit message. Their algorithm solves this task in $O(d^{1.907})$ rounds, while the trivial bound is $O(d^2)$. We improve on the prior work in two dimensions: First, we show that we can solve the same task faster, in only $O(d^{1.832})$ rounds.

Second, we explore what happens when matrices are not uniformly sparse. We consider the following alternative notions of sparsity: row-sparse matrices (at most $d$ non-zeros per row), column-sparse matrices, matrices with bounded degeneracy (we can recursively delete a row or column with at most $d$ non-zeros), average-sparse matrices (at most $dn$ non-zeros in total), and general matrices.

We present a near-complete classification of the complexity of matrix multiplication in the above setting for all combinations of these notions of sparsity.

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdős, Simonovits and Sós. For given graphs $G$ and $H$ the anti-Ramsey number $ar(G,H)$ is defined to be the maximum number $k$ such that there exists an assignment of $k$ colors to the edges of $G$ in which every copy of $H$ in $G$ has at least two edges with the same color.

Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when $H$ is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number $ar(G,P_k)$, where $P_k$ is a path of length $k$. First, we observe that when $k$ is close to $n$ (the number of vertices in $G$), the problem is hard; hence, the challenging part is the computational complexity of the problem when $k$ is a fixed constant.

We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing $ar(G,P_k)$ for every integer $k\ge 3$ is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant $k$.

In prior work, Gupta et al. (SPAA 2022) presented a distributed algorithm for multiplying sparse $n\times n$ matrices, using $n$ computers. They assumed that the input matrices are uniformly sparse—there are at most $d$ non-zeros in each row and column—and the task is to compute a uniformly sparse part of the product matrix. Initially each computer knows one row of each input matrix, and eventually each computer needs to know one row of the product matrix. In each communication round each computer can send and receive one $O(\log n)$-bit message. Their algorithm solves this task in $O(d^{1.907})$ rounds, while the trivial bound is $O(d^2)$.

We improve on the prior work in two dimensions: First, we show that we can solve the same task faster, in only $O(d^{1.832})$ rounds. Second, we explore what happens when matrices are not uniformly sparse. We consider the following alternative notions of sparsity: row-sparse matrices (at most $d$ non-zeros per row), column-sparse matrices, matrices with bounded degeneracy (we can recursively delete a row or column with at most $d$ non-zeros), average-sparse matrices (at most $dn$ non-zeros in total), and general matrices.

We show that we can still compute $X=AB$ in $O(d^{1.832})$ rounds even if one of the three matrices ($A$, $B$, or $X$) is average-sparse instead of uniformly sparse. We present algorithms that handle a much broader range of sparsity in $O(d^2+\log n)$ rounds, and present conditional hardness results that put limits on further improvements and generalizations.

We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in $O(\log D)$ rounds in the massively parallel computation model (MPC), with $O(n^{\delta })$ words of local memory per machine, for any given constant $0<\delta <1$. Here $D$ is the diameter of the tree and $n$ is the number of nodes—we emphasize that our running time is independent of $n$.

Our algorithm can solve many classical graph optimization problems such as maximum weight independent set, maximum weight matching, minimum weight dominating set, and minimum weight vertex cover. It can also be used to solve many accumulation tasks in which some aggregate information is propagated upwards or downwards in the tree—this includes, for example, computing the sum, minimum, or maximum of the input labels in each subtree, as well as many inference tasks commonly solved with belief propagation. Our algorithm can also solve any locally checkable labeling problem (LCLs) in trees. Our algorithm works for any reasonable representation of the input tree; for example, the tree can be represented as a list of edges or as a string with nested parentheses or tags. The running time of $O(\log D)$ rounds is also known to be necessary, assuming the widely-believed $2$-cycle conjecture.

Our algorithm strictly improves on two prior algorithms:

(1) Bateni, Behnezhad, Derakhshan, Hajiaghayi, and Mirrokni [ICALP'18] solve problems of these flavors in $O(\log n)$ rounds, while our algorithm is much faster in low-diameter trees. Furthermore, their algorithm also uses randomness, while our algorithm is deterministic.

(2) Balliu, Latypov, Maus, Olivetti, and Uitto [SODA'23] solve only locally checkable labeling problems in $O(\log D)$ rounds, while our algorithm can be applied to a much broader family of problems.

The minimum directed spanning tree (MDST) problem has until recently not been studied in distributed computing models. This fundamental task generalizes the well-studied minimum spanning tree problem, by asking for a minimum weight spanning tree rooted at some specified node of a directed network. In their DISC 2019 paper [9], Fischer and Oshman reduce the MDST problem to the single-source shortest path (SSSP) problem, with a polylogarithmic increase in running time. This holds both in the Congest and Congested Clique models. Fischer and Oshman further suggest the possibility that an approximate SSSP algorithm could be leveraged in computing an approximate MDST. We extend their analysis to show that this is indeed the case: For $\epsilon >0$, using a $(1+\epsilon )$-approximation to SSSP running in $R$ rounds we can compute a $(1+\epsilon )$-approximate MDST in $\tilde{O}(R)$ rounds ($\tilde{O}$-notation neglects polylogarithmic factors in the number $n$ of nodes in the graph.). In particular, this implies the following improvements in the state of the art for $(1+o(1))$-approximation of MDST.

An $\tilde{O}(n^{1-2/\omega +o(1)})\subset \tilde{O}(n^{0.158})$-round Congested Clique algorithm, where $\omega <2.373$ is the fast matrix multiplication exponent [3].

An $\tilde{O}({\lambda }^2)$-round Congested Clique algorithm in graphs where each edge has an at most factor $\lambda \ge 1$ heavier reverse edge [1].

An $\tilde{O}({\lambda }^2(\sqrt{n}+D))$-round Congest algorithm in the same family of graphs [1]. For $\lambda \in {\log }^{O(1)}n$, the resulting running time of $\tilde{O}(\sqrt{n}+D)$ is unconditionally tight up to a polylogarithmic factor [21].

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs $G$ and $H$ the anti-Ramsey number $ar(G,H)$ is defined to be the maximum number $k$ such that there exists an assignment of $k$ colors to the edges of $G$ in which every copy of $H$ in $G$ has at least two edges with the same color.

Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when $H$ is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number $ar(G,P_k)$, where $P_k$ is a path of length $k$. First, we observe that when $k$ is close to $n$, the problem is hard; hence, the challenging part is the computational complexity of the problem when $k$ is a fixed constant.

We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing $ar(G,P_k)$ for every integer $k>2$ is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating $ar(G,P_3)$ to a factor of $n^{-1/2-ϵ}$ is hard already in $3$-partite graphs, unless $P=NP$. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant $k$.

Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. Along this line, we first introduce the notion of color connected coloring, and, employing this structural property, we obtain a linear time algorithm to compute $ar(G,P_k)$, for every integer $k$, when the host graph, $G$, is a tree.