arXiv:1608.02674v1 [cs.DC] 9 Aug 2016

Further Algebraic Algorithms in the Congested Clique Model and
Applications to Graph-Theoretic Problems
François Le Gall
Graduate School of Informatics
Kyoto University
legall@i.kyoto-u.ac.jp

Abstract
Censor-Hillel et al. [PODC’15] recently showed how to efficiently implement centralized algebraic algorithms for matrix multiplication in the congested clique model, a model of distributed
computing that has received increasing attention in the past few years. This paper develops
further algebraic techniques for designing algorithms in this model. We present deterministic
and randomized algorithms, in the congested clique model, for efficiently computing multiple
independent instances of matrix products, computing the determinant, the rank and the inverse of a matrix, and solving systems of linear equations. As applications of these techniques,
we obtain more efficient algorithms for the computation, again in the congested clique model,
of the all-pairs shortest paths and the diameter in directed and undirected graphs with small
weights, improving over Censor-Hillel et al.’s work. We also obtain algorithms for several other
graph-theoretic problems such as computing the number of edges in a maximum matching and
the Gallai-Edmonds decomposition of a simple graph, and computing a minimum vertex cover
of a bipartite graph.

1

Introduction

Background. The congested clique model is a model in distributed computing that has recently
received increasing attention [5, 12, 13, 17, 18, 19, 20, 26, 27, 30, 34, 35]. In this model n nodes
communicate with each other over a fully-connected network (i.e., a clique) by exchanging messages
of size O(log n) in synchronous rounds. Compared with the more traditional congested model [36],
the congested clique model removes the effect of distances in the computation and thus focuses
solely on understanding the role of congestion in distributed computing.
Typical computational tasks studied in the congested clique model are graph-theoretic problems
[5, 12, 13, 17, 20, 34], where a graph G on n vertices is initially distributed among the n nodes of the
network (the ℓ-th node of the network knows the set of vertices adjacent to the ℓ-th vertex of the
graph, and the weights of the corresponding edges if the graph is weighted) and the nodes want to
compute properties of G. Besides their theoretical interest and potential applications, such problems
have the following natural interpretation in the congested clique model: the graph G represents the
actual topology of the network, each node knows only its neighbors but can communicate to all the
nodes of the network, and the nodes want to learn information about the topology of the network.
Censor-Hillel et al. [5] recently developed algorithms for several graph-theoretic problems in the
congested clique model by showing how to implement centralized algebraic algorithms for matrix
multiplication in this model. More precisely, they constructed a O(n1−2/ω )-round algorithm for
matrix multiplication, where ω denotes the exponent of matrix multiplication (the best known
upper bound on ω is ω < 2.3729, obtained in [25, 43], which gives exponent 1 − 2/ω < 0.1572
in the congested clique model), improving over the O(n2−ω ) algorithm mentioned in [13], in the
following setting: given two n × n matrices A and B over a field, the ℓ-th node of the network
initially owns the ℓ-th row of A and the ℓ-column of B, and needs to output the ℓ-th row and the ℓcolumn of the product AB. Censor-Hillel et al. consequently obtained O(n1−2/ω )-round algorithms
for several graph-theoretic tasks that reduce to computing the powers of (some variant of) the
adjacency matrix of the graph, such as counting the number of triangles in a graph (which lead to
an improvement over the prior best algorithms for this task [12, 13]), detecting the existence of a
constant-length cycle and approximating the all-pairs shortest paths in the input graph (improving
the round complexity obtained in [34]). One of the main advantages of such an algebraic approach
in the congested clique model is its versatility: it makes possible to construct fast algorithms for
graph-theoretic problems, and especially for problems for which the best non-algebraic centralized
algorithm is highly sequential and does not seem to be implementable efficiently in the congested
clique model, simply by showing a reduction to matrix multiplication (and naturally also showing
that this reduction can be implemented efficiently in the congested clique model).
Our results. In this paper we develop additional algebraic tools for the congested clique model.
We first consider the task of computing in the congested clique model not only one matrix
product, but multiple independent matrix products. More precisely, given k matrices A1 , . . . , Ak
each of size n × m and k matrices B1 , . . . , Bk each of size m × m, initially evenly distributed among
the n nodes of the network, the nodes want to compute the k matrix products A1 B1 , . . . , Ak Bk .
Prior works [5, 13] considered only the case k = 1 and m = n, i.e., one product of two square
matrices. Our contribution is thus twofold: we consider the rectangular case, and the case of
several matrix products as well. Let us first discuss our results for square matrices (m = n). By
using sequentially k times the matrix multiplication algorithm from [5], k matrix products can
naturally be computed in O(kn1−2/ω ) rounds. In this work we show that we can actually do better.
2

Theorem 1 (Simplified version). In the congested clique model k independent products of pairs of
n × n matrices can be computed with round complexity

O(k2/ω n1−2/ω ) if 1 ≤ k < n,
O(k)
if k ≥ n.
This generalization of the results from [5] follows from a simple strategy: divide the n nodes
of the network into k blocks (when k ≤ n), each containing roughly n/k nodes, compute one of
the k matrix products per block by using an approach similar to [5] (i.e., a distributed version of
the best centralized algorithm computing one instance of square matrix multiplication), and finally
distribute the relevant part of the k output matrices to all the nodes of the network. Analyzing
the resulting protocol shows that the dependence in k in the overall round complexity is reduced
to k2/ω . This sublinear dependence in k has a significant number of implications (see below).
The complete version of Theorem 1, given in Section 3, also considers the general case where the
matrices may not be square (i.e., the case m 6= n), which will be crucial for some of our applications
to the All-Pairs Shortest Path problem. The proof becomes more technical than for the square case,
but is conceptually very similar: the main modification is simply to now implement a distributed
version of the best centralized algorithm for rectangular matrix multiplication. The upper bounds
obtained on the round complexity depend on the complexity of the best centralized algorithms for
rectangular matrix multiplication (in particular the upper bounds given in [24]). Figure 1 depicts
the upper bounds we obtain for the case k = 1. While the major open problem is still whether
the product of two square matrices can be computed in a constant (or nearly constant) number of
rounds, our results show that for m = O(n0.651... ), the product of an n × m matrix by an m × n
matrix can indeed be computed in O(nǫ ) rounds for any ǫ > 0. We also show lower bounds on the
round complexity of the general case (Proposition 1 in Section 3), which are tight for most values
of k and m, based on simple arguments from communication complexity.

Round complexity

n1

n0.5

n0.1572
n0
n0

n0.5 n0.651...
n1
n2
Value of m
Figure 1: Our upper bounds on the round complexity of the computation of the product of an
n × m matrix by an m × n matrix in the congested clique model.
We then study the following basic problems in linear algebra: computing the determinant, the
rank or the inverse of an n × n matrix over a finite field F of order upper bounded by a polynomial
of n, and solving a system of n linear equations and n variables. We call these problems DET(n, F),
3

Rank(n, F), INV(n, F) and SYS(n, F), respectively (the formal definitions are given in Section 2).
While it is known that in the centralized setting these problems can be solved with essentially the
same time complexity as matrix multiplication [4], these reductions are typically sequential and do
not work in a parallel setting. In this paper we design fast deterministic and randomized algorithm
for these four basis tasks, and obtain the following results.
Theorem 2. Assume that F has characteristic greater than n. In the congested clique model, the
deterministic round complexity of DET(n, F) and INV(n, F) is O(n1−1/ω ).
Theorem 3. Assume that F has order |F| = Ω(n2 log n). In the congested clique model, the
randomized round complexity of DET(n, F), SYS(n, F) and Rank(n, F) is O(n1−2/ω log n).
The upper bounds of Theorems 2 and 3 are O(n0.5786 ) and O(n0.1572 ), respectively, by basing
our implementation on the asymptotically fastest (but impractical) centralized algorithm for matrix
multiplication corresponding to the upper bound ω < 2.3729. These bounds are O(n2/3 ) and
O(n1/3 log n), respectively, by basing our implementation on the trivial (but practical) centralized
algorithm for matrix multiplication (corresponding to the bound ω ≤ 3). These algorithms are
obtained by carefully adapting to the congested clique model the relevant known parallel algorithms
[9, 21, 22, 23, 37] for linear algebra, and using our efficient algorithm for computing multiple matrix
products (Theorem 1) as a subroutine. An interesting open question is whether INV(n, F) can be
solved with the same (randomized) round complexity as the other tasks. This problem may very
well be more difficult; in the parallel setting in particular, to the best of our knowledge, whether
matrix inversion can be done with the same complexity as these other tasks is also an open problem.
Applications of our results. The above results give new algorithms for many graph-theoretic
problems in the congested clique model, as described below and summarized in Table 1.
Our main key tool to derive these applications is Theorem 7 in Section 3, which gives an
algorithm computing efficiently the distance product (defined in Section 2) of two matrices with
small integer entries based on our algorithm for multiple matrix multiplication of Theorem 1.
Computing the distance product is a fundamental graph-theoretic task deeply related to the AllPairs Shortest Path (APSP) problem [40, 41, 47]. Combining this result with techniques from [41],
and observing that these techniques can be implemented efficiently in the congested clique model,
we then almost immediately obtain the following result.
Theorem 4. In the congested clique model, the deterministic round complexity of the all-pairs
shortest paths problem in an undirected graph of n vertices with integer weights in {0, . . . , M },
where M is an integer such that M ≤ n, is Õ(M 2/ω n1−2/ω ).
Since computing the diameter of a graph reduces to solving the all-pairs shortest paths, we
obtain the same round complexity for diameter computation in the same class of graphs. This
improves over the Õ(M n1−2/ω )-round algorithm for these tasks (implicitly) given in [5]. The main
application of our results nevertheless concerns the all-pair shortest paths problem over directed
graphs (for which the approach based on [41] does not work) with constant weights. We obtain
the following result by combining our algorithm for distance product computation with Zwick’s
approach [47].
Theorem 5. In the congested clique model, the randomized round complexity of the all-pairs shortest paths problem in a directed graph of n vertices with integer weights in {−M, . . . , 0, . . . , M },
where M = O(1), is O(n0.2096 ).
4

Table 1: Summary of the applications of our algebraic techniques to graph-theoretic problems in
the congested clique model. Here n both represents the number of vertices in the input graph and
the number of nodes in the network.
Problem
APSP (undirected graphs, weights in {0, 1, . . . , M })

Round
 2 complexity

2
Õ M ω n1− ω Th. 4

O(n0.2096 )
 2

2
Diameter (undirected graphs, weights in {0, 1, . . . , M }) Õ M ω n1− ω

2
Computing the size of a maximum matching
O n1− ω log n
Computing allowed edges in a perfect matching
O(n1−1/ω )
Gallai-Edmonds decomposition
O(n1−1/ω )
Minimum vertex cover in bipartite graphs
O(n1−1/ω )
APSP (directed graphs, constant weights)

Th. 5

Cor. 1
Th. 8
Sec. 6.3
Th. 9
Sec. 6.4

Previously


2
Õ M n1− ω
Õ(n1/3 )


2
Õ M n1− ω
—
—
—
—

Prior to this work, the upper bound for the round complexity of this problem was Õ(n1/3 ), obtained
by directly computing the distance product (as done in [5]) in the congested clique model. Again,
Theorem 5 follows easily from Theorem 7 and the observation that the reduction to distance
product computation given in [47] can be implemented efficiently in the congested clique model.
The exponent 0.2096 in the statement of Theorem 5 is derived from the current best upper bounds
on the complexity of rectangular matrix multiplication in the centralized setting [24].
Theorems 2 and 3 also enable us to solve a multitude of graph-theoretic problems in the congested clique model with a sublinear number of rounds. Examples described in this paper are
computing the number of edges in a maximum matching of a simple graph with O(n1−2/ω log n)
rounds, computing the set of allowed edges in a perfect matching, the Gallai-Edmonds decomposition of a simple graph, and a minimum vertex cover in a bipartite graph with O(n1−1/ω ) rounds.
These results are obtained almost immediately from the appropriate reductions to matrix inversion
and similar problems known the centralized setting [7, 31, 38] — indeed it is not hard to adapt all
these reductions so that they can be implemented efficiently in the congested clique model. Note
that while non-algebraic centralized algorithms solving these problems also exist (see, e.g., [32]),
they are typically sequential and do not appear to be efficiently implementable in the congested
clique model. The algebraic approach developed in this paper, made possible by our algorithms for
the computation of the determinant, the rank and the inverse of matrix, appears to be currently
the only way of obtaining fast algorithms for these problems in the congested clique model.

2

Preliminaries

Notations. Through this paper we will use n to denote the number of nodes in the network.
The n nodes will be denoted 1, 2, . . . , n. The symbol F will always denote a finite field of order
upper bounded by a polynomial in n (which means that each field element can be encoded with
O(log n) bits and thus sent using one message in the congested clique model). Given any positive
integer p, we use the notation [p] to represent the set {1, 2, . . . , p}. Given any p × p′ matrix A, we
will write its entries as A[i, j] for (i, j) ∈ [p] × [p′ ], and use the notation A[i, ∗] to represent its i-th
row and A[∗, j] to represent its j-th column.

5

Graph-theoretic problems in the congested clique model. As mentioned in the introduction, typically the main tasks that we want to solve in the congested clique model are graphtheoretical problems. In all the applications given in this paper the number of vertices of the graph
will be n, the same as the number of nodes of the network. The input will be given as follows:
initially each node ℓ ∈ [n] has the ℓ-th row and the ℓ-th column of the adjacency matrix of the
graph. Note that this distribution of the input, while being the most natural, is not essential; the
only important assumption is that the entries are evenly distributed among the n nodes since they
can then be redistributed in a constant number of rounds as shown in the following Lemma by
Dolev et al. [12], which we will use many times in this paper.
Lemma 1. [12] In the congested clique model a set of messages in which no node is the source
of more than n messages and no node is the destination of more than n messages can be delivered
within two rounds if the source and destination of each message is known in advance to all nodes.
Algebraic problems in the congested clique model.
we consider in this paper are defined as follows.

The five main algebraic problems that

MM(n, m, k, F) — Multiple Rectangular Matrix Multiplications
Input: matrices A1 , . . . , Ak ∈ Fn×m and B1 , . . . , Bk ∈ Fm×n distributed among the n nodes
(Node ℓ ∈ [n] has A1 [ℓ, ∗], . . . , Ak [ℓ, ∗] and B1 [∗, ℓ], . . . , Bk [∗, ℓ])
Output: the matrices A1 B1 , . . . , Ak Bk distributed among the n nodes
(Node ℓ ∈ [n] has A1 B1 [ℓ, ∗], . . . , Ak Bk [ℓ, ∗] and A1 B1 [∗, ℓ], . . . , Ak Bk [∗, ℓ])
DET(n, F) — Determinant
Input: matrix A ∈ Fn×n distributed among the n nodes (Node ℓ ∈ [n] has A[ℓ, ∗] and A[∗, ℓ])
Output: det(A) (Each node of the network has det(A))
Rank(n, F) — Rank
Input: matrix A ∈ Fn×n distributed among the n nodes (Node ℓ ∈ [n] has A[ℓ, ∗] and A[∗, ℓ])
Output: rank(A) (Each node of the network has rank(A))
INV(n, F) — Inversion
Input: invertible matrix A ∈ Fn×n distributed among the n nodes
(Node ℓ ∈ [n] has A[ℓ, ∗] and A[∗, ℓ])
Output: matrix A−1 distributed among the n nodes (Node ℓ ∈ [n] has A−1 [ℓ, ∗] and A−1 [∗, ℓ])
(Node ℓ ∈ [n] has A−1 [ℓ, ∗] and A−1 [∗, ℓ])
SYS(n, F) — Solution of a linear system
Input: invertible matrix A ∈ Fn×n and vector b ∈ Fn×1 , distributed among the n nodes
(Node ℓ ∈ [n] has A[ℓ, ∗], A[∗, ℓ] and b)
Output: the vector x ∈ Fn×1 such that Ax = b (Node ℓ ∈ [n] has x[ℓ])
Note that the distribution of the inputs and the outputs assumed in the above five problems
is mostly chosen for convenience. For instance, if needed the whole vector x in the output of
SYS(n, F) can be sent to all the nodes of the network in two rounds using Lemma 1. The only
important assumption is that when dealing with matrices, the entries of the matrices must be
evenly distributed among the n nodes.
We will also in this paper consider the distance product of two matrices, defined as follows.
6

Definition 1. Let m and n be two positive integers. Let A be an n × m matrix and B be an m × n
matrix, both with entries in R ∪ {∞}. The distance product of A and B, denoted A ∗ B, is the
n × n matrix C such that C[i, j] = mins∈[m] {A[i, s] + B[s, j]} for all (i, j) ∈ [n] × [n].
We will be mainly interested in the case when the matrices have integer entries. More precisely,
we will consider the following problem.
DIST(n, m, M ) — Computation of the distance product
Input: an n×m matrix A and an m×n matrix B, with entries in {−M, . . . , −1, 0, 1, . . . , M }∪{∞}
(Node ℓ ∈ [n] has A[ℓ, ∗] and B[∗, ℓ])
Output: the matrix C = A ∗ B distributed among the n nodes
(Node ℓ ∈ [n] has C[ℓ, ∗] and C[∗, ℓ])
Centralized algebraic algorithms for matrix multiplication. We now briefly describe algebraic algorithms for matrix multiplication and known results about the complexity of rectangular
matrix multiplication. We refer to [4] for a detailed exposition of these concepts.
Let F be a field and m, n be two positive integer. Consider the problem of computing the
product of an n × m matrix by an m × n matrix over F. An algebraic algorithm for this problem
is described by three sets {αijµ }, {βijµ } and {λijµ } of coefficients from F such that, for any n × m
matrix A and any m × n matrix B, the equality
C[i, j] =

t
X

λijµ S (µ) T (µ)

µ=1

holds for all (i, j) ∈ [n] × [n], where C = AB and
S (µ) =

m
n X
X

T (µ) =

αijµ A[i, j],

m
n X
X

βijµ B[j, i],

i=1 j=1

i=1 j=1

for each s ∈ [t]. Note that each S (µ) and each T (µ) is an element of F. The integer t is called the
rank of the algorithm, and corresponds to the complexity of the algorithm.
For instance, consider the trivial algorithm computing this matrix product using the formula
C[i, j] =

m
X

A[i, s]B[s, j].

s=1

This algorithm can be described in the above formalism by taking t = n2 m, writing each µ ∈ [n2 m]
as a triple µ = (i′ , j ′ , s′ ) ∈ [n] × [n] × [m], and choosing

1 if i = i′ and j = j ′ ,
λij(i′ ,j ′ ,s′ ) =
0 otherwise,


1 if i = i′ and j = s′ ,
1 if i = j ′ and j = s′ ,
αij(i′ ,j ′ ,s′ ) =
βij(i′ ,j ′ ,s′ ) =
0 otherwise,
0 otherwise.
Note that this trivial algorithm, and the description we just gave, also works over any semiring.

7

The exponent of matrix multiplication. For any non-negative real number γ, let ω(γ) denote
the minimal value τ such that the product of an n × ⌈nγ ⌉ matrix over F by an ⌈nγ ⌉ × n matrix
over F can be computed by an algebraic algorithm of rank nτ +o(1) (i.e., can be computed with
complexity O(nτ +ǫ ) for any ǫ > 0). As usual in the literature, we typically abuse notation and
simply write that such a product can be done with complexity O(nω(γ) ), i.e., ignoring the o(1) in
the exponent. The value ω(1) is denoted by ω, and often called the exponent of square matrix
multiplication. Another important quantity is the value α = sup{γ | ω(γ) = 2}.
The trivial algorithm for matrix multiplication gives the upper bound ω(γ) ≤ 2 + γ, and thus
ω ≤ 3 and α ≥ 0. The current best upper bound on ω is ω < 2.3729, see [25, 43]. The current best
bound on α is α > 0.3029, see [24]. The best bounds on ω(γ) for γ > α can also be found in [24].

3

Matrix Multiplication in the Congested Clique Model

In this section we present our results on the round complexity of MM(n, m, k, F) and DIST(n, m, M ).
We first give the complete statement of our main result concerning MM(n, m, k, F) that was
stated in a simplified form in the introduction.
Theorem 1 (Complete version). For any positive integer k ≤ n, the deterministic round complexity
of MM(n, m, k, F) is
√

if √
0 ≤ m ≤ kn,
 O(k)
kn ≤ m < n2 /k,
O(k2/ω(γ) n1−2/ω(γ) ) if

O(km/n)
if m ≥ n2 /k,

where γ is the solution of the equation




log m
log k
log k
+
− 1 ω(γ).
γ =1−
1−
log n
log n
log n

(1)

For any k ≥ n, the deterministic round complexity of MM(n, m, k, F) is

O(k)
if 1 ≤ m ≤ n,
O(km/n) if m ≥ n.
The proof
√ of Theorem 1, which will also show that Equation (1) always has a solution when
k ≤ n and kn ≤ m < n2 /k, is given in Section 3.1 (a short discussion of the proof ideas was
presented in the introduction). The upper bounds we obtain for the case k = 1 are depicted
in Figure 1, where Equation (1) is solved using the best known upper bound on ω(γ) from [24].
√
As briefly mentioned in the introduction, the round complexity is constant for any k ≤ n, and
we further have round complexity O(nǫ ), for any ǫ > 0, for all values k ≤ n(1+α)/2 (the bound
α > 0.3029 implies (1 + α)/2 > 0.6514). For the case m = n the solution of Equation (1) is γ = 1,
which gives the bounds of the simplified version of Theorem 1 presented in the introduction.
We now give lower bounds on the round complexity of MM(n,
m, k, F) that show that the upper
√
bounds of Theorem 1 are tight, except possibly in the case kn ≤ m < n2 /k when k ≤ n.
Proposition 1. The randomized round complexity of MM(n, m, k, F) is

Ω(k)
if 1 ≤ m ≤ n,
Ω(km/n) if m ≥ n.
8

Proof. We first prove the lower bound Ω(km/n) for any m ≥ n. Let us consider instances of
MM(n, m, k, F) of the following form: for each s ∈ [k] all the rows of As are zero except the first row;
for each s ∈ [k] all the columns of Bs are zero except the second column. Let us write Cs = As Bs
for each s ∈ [k]. We prove the lower bound by partitioning the n nodes of the network into
the two sets {1} and {2, . . . , n}, and considering the following two-party communication problem.
Alice (corresponding to the set {1}) has for input As [1, j] for all j ∈ [m] and all s ∈ [k]. Bob
(corresponding to the set {2, . . . , n}) has for input Bs [i, 2] for all i ∈ [m] and all s ∈ [k]. The goal is
for Alice to output Cs [1, 2] for all s ∈ [k]. Note that
P Cs [1, 2] is the inner product (over F) of the first
row of As and the second column of Bs . Thus ks=1 Cs [1, 2] is the inner product of two vectors of
size km. Alice and Bob must exchange Ω(km log |F|) bits to compute this value [8], which requires
Ω(km/n) rounds in the original congested clique model.
We now prove the lower bound Ω(k) for any m ≥ 1. Let us consider instances of MM(n, m, k, F)
of the following form: for each s ∈ [k], all entries of As are zero except the entry As [1, 1] which is
one; for each s ∈ [k], Bs [i, j] = 0 for all (i, j) ∈
/ {(1, j) | j ∈ {2, . . . , n}} (the other n − 1 entries are
arbitrary). Again, let us write Cs = As Bs for each s ∈ [k]. We prove the lower bound by again
partitioning the n nodes of the network into the two sets {1} and {2, . . . , n}, and considering the
following two-party communication problem. Alice has no input. Bob has for input Bs [1, j] for all
j ∈ {2, . . . , n} and all s ∈ [k]. The goal is for Alice to output Cs [1, j] for all j ∈ {2, . . . , n} and all
s ∈ [k]. Since the output reveals Bob’s whole input to Alice, Alice must receive Ω(k(n − 1) log |F|)
bits, which gives round complexity Ω(k) in the original congested clique model.

3.1

Proof of Theorem 1

Let us first prove the following proposition that deals with the case where m is large. In this case
the algorithm is relatively simple.
Proposition 2. For any k ≤ n and any m ≥ n2 /k, the deterministic round complexity of
MM(n, m, k, F) is O(km/n).
Proof. We assume below for convenience that both n/k and km/n are integers. If this is not
the case the proof can be adjusted in a straightforward manner by replacing them by ⌈n/k⌉ and
⌈km/n⌉, respectively.
For each s ∈ [k], we will write Cs = As Bs . Let us decompose the matrix As into n/k matrices
of size n × km
n by partitioning the m columns of As into n/k consecutive blocks of size km/n. Let
(1)

(n/k)

us call these smaller matrices As , . . . , As
. Similarly, for each s ∈ [k] we decompose the matrix
km
Bs into n/k matrices of size n × n by partitioning the m rows of Bs into n/k consecutive blocks
(1)

(n/k)

of size km/n. Let us call these smaller matrices Bs , . . . , Bs
(t)
(t) (t)
Cs = As Bs .
For each s ∈ [k], and each i, j ∈ [n] the equation
Cs [i, j] =

n/k
X

Cs(t) [i, j]

. For each t ∈ [n/k] we write

(2)

t=1

obviously holds. Our distributed algorithm is based on this simple observation. Each node of the
network will be assigned, besides its original label ℓ ∈ [n], a second label (s, t) ∈ [k] × [n/k]. The
assignment of these labels is arbitrary, the only condition being that distinct nodes are assigned
distinct labels. The distributed algorithm is as follows.
9

(t)

(t)

1. Node (s, t) ∈ [k] × [n/k] receives the whole two matrices As and Bs from the nodes of the
(t)
networks owning the entries of these two matrices, and then locally computes Cs .
(t)

(t)

2. Node ℓ ∈ [n] receives Cs [ℓ, ∗] and Cs [∗, ℓ] for all s ∈ [k] and all t ∈ [n/k] from the nodes
of the network owning these entries, and then locally computes Cs [ℓ, ∗] and Cs [∗, ℓ] using
Equation (2) for all s ∈ [k].

The number of field elements received per node is 2km at Step 1 and 2n2 at Step 2. The total
number of field elements received per node is thus O(km + n2 ), which gives round complexity
O(km/n) when km ≥ n2 from Lemma 1.

The main technical contribution is the following proposition.
√
Proposition 3. For any k and m such that k ≤ n and kn ≤ m < n2 /k, the deterministic round
complexity of MM(n, m, k, F) is
O(k2/ω(γ) n1−2/ω(γ) ),

log k 
log m
log k
where γ is the solution of the equation 1 − log
n γ = 1 − log n + log n − 1 ω(γ).

Proof. For convenience, let us assume that n/k is an integer (otherwise we replace this value by the
nearest integer). Let γ ≥ 0 be a value that will be set later. Let d be the largest integer such that
the product of a d × ⌈dγ ⌉ matrix by a ⌈dγ ⌉ × d matrix can be computed by an algebraic algorithm
(as in Section 2) of rank n/k. Note that


d = Θ (n/k)1/ω(γ)
from the definition
of√the exponent of matrix multiplication. For convenience, we assume below
p
that n/d, n/k and kn/d are also integers (otherwise we can again simply replace these values
by the nearest integer). Define the quantity


m
m
r= p
=Θ
.
(n/k)γ/ω(γ)+1/2
dγ n/k

Our choice of γ (discussed later) will guarantee that m ≥ (n/k)γ/ω(γ)+1/2 , which implies r = Ω(1).
We will thus assume below, for convenience but without affecting the analysis of the complexity of
the algorithm, that r and dγ are integers such that r ≥ 1 and dγ ≤ m, and that m/dγ is an integer
as well.
For each s ∈ [k], we write the entries of As and Bs as As [ix, jz] and Bs [jz, ix], respectively,
where i ∈ [d], j ∈ [dγ ], x ∈ [n/d] and z ∈ [m/dγ ]. More precisely, this notation corresponds to
decomposing each row of As and each column of Bs into d consecutive blocks of n/d entries, and
decomposing each column of As and each row of Bs into dγ consecutive blocks of m/dγ entries.
Note that this corresponds to decomposing As into an d×dγ matrix where each entry is a submatrix
of As of size (n/d) × (m/dγ ), and decomposing Bs into an dγ × d matrix where each entry is a
submatrix of Bs of size (m/dγ ) × (n/d). We will write As [i∗, j∗] and Bs [j∗, i∗] to represent these
submatrices. Similarly, we write the elements of the output matrix Cs = As Bs as Cs [ix, jy], where
i, j ∈ [d] and x, y ∈ [n/d]. By extending the formulation given in Section 2 to block matrices (and
using the same notations), for any s ∈ [k], any i, j ∈ [d] and any x, y ∈ [n/d] we can write
Cs [ix, jy] =

n/k
X

µ=1

10

λijµ Ss(µ) Ts(µ) ,

(3)

(µ)

where, for each µ ∈ [n], Ss is an (n/d)×(m/dγ ) matrix that can be written as a linear combination
(µ)
of the submatrices of As , and Ts is an (m/dγ ) × (n/d) matrix that can be written as a linear
combination of the submatrices of Bs :
γ

Ss(µ)

=

d X
d
X

αijµ As [i∗, j∗]

(4)

βijµ Bs [j∗, i∗].

(5)

i=1 j=1
γ

Ts(µ)

=

d X
d
X
i=1 j=1

Finally, we will also decompose each label x, y and z into two parts:
p
√
• we write x = wx′ where w ∈ [ n/k] and x′ ∈ [ kn/d],
√
p
• we write y = wy ′ where w ∈ [ n/k] and y ′ ∈ [ kn/d],
p
• we write z = wz ′ where w ∈ [ n/k] and z ′ ∈ [r].

p
p
This corresponds to further decomposing each submatrix
of As into an n/k × n/k matrix where
√
each entry
submatrix of As of size ( kn/d) × r, and decomposing each submatrix
p
√ of Bs
p is a smaller
into an n/k × n/k matrix where each entry is a smaller submatrix of Bs of size r × ( kn/d).
Each node of the network has a label (i, x) ∈ [d] × [n/d], and receives as input As [ix, ∗] and
Bp
[∗,
ix] forpall s ∈ [k]. We assign two additional labels to each node: one label (s, u, v) ∈ [k] ×
s
[ n/k] × [ n/k] and one label (s, µ) ∈ [k] × [n/k]. The assignment of these labels is arbitrary,
the only condition being that distinct nodes are assigned distinct labels. The algorithm is given in
Figure 2.
The number of field elements received per node at Step 1 is
√
m
kn
γ
× p
= 2km.
2×d×d ×
γ
d
d n/k
The number of field elements received per node at Step 2 is


m
n
(6)
2 × × γ = O k(1+γ)/ω(γ) mn1−(1+γ)/ω(γ) .
d d
The number of field elements received per node at Step 3 is
√
√


n
kn
kn
(7)
×
×
= O k2/ω(γ) n2−2/ω(γ) .
k
d
d
The number of field elements received per node at Step 4 is 2kn. Note that Expression (6) is larger
than 2km since ω(γ) ≥ 1+ γ and k ≤ n. Moreover, Expression (7) is larger than 2kn since ω(γ) ≥ 2
and k ≤ n. Thus the total number of field elements received per node is


O k(1+γ)/ω(γ) mn1−(1+γ)/ω(γ) + k2/ω(γ) n2−2/ω(γ) .
Let us write a = log k/ log n and b = log m/ log n and define the two functions
a(1 + γ)
1+γ
+b+1−
,
ω(γ)
ω(γ)
2a
2
g(γ) =
+2−
,
ω(γ)
ω(γ)

f (γ) =

11

p
p
1. Node (s, u, v) ∈ [k] × [ n/k] × [ n/k] receives As [iux′ , jvz ′ ] and Bs [juz ′ , ivy√′ ] from
the nodes of the network owning these entries, for all i ∈ [d], j ∈ [dγ ], x′ , y ′ ∈ [ kn/d]
(µ)
and z ′ ∈ [r]. Node (s, u, v) then locally computes Ss [ux′ , vz ′ ] using Equation (4)
√
(µ)
and Ts [uz ′ , vy ′ ] using Equation (5) for all µ ∈ [n/k], all x′ , y ′ ∈ [ kn/d] and all
z ′ ∈ [r].
(µ)

(µ)

2. Node (s, µ) ∈ [k] × [n/k] receives the whole matrices Ss and Ts from the nodes of
the network owning the entries of these matrices, and locally computes the product
(µ)
(µ) (µ)
Ps = Ss Ts .
p
p
(µ)
3. Node (s, u, v) ∈ [k] × [ n/k] × [ n/k] receives Ps [ux′ , vy ′ ] from√the nodes of
the network owning these entries, for all µ ∈ [n/k] and all x′ , y ′ ∈ [ kn/d]. Node
′
′
(s, u, v) then
√ locally computes Cs [iux , jvy ] using Equation (3) for all i, j ∈ [d] and
′
′
all x , y ∈ [ kn/d].
4. Node (i, x) ∈ [d] × [n/d] receives Cs [ix, ∗] and Cs [∗, ix] for all s ∈ [k] from the nodes
of the network owning these entries.
Figure 2: Distributed algorithm for MM(n, m, k, F) in the congested clique model. Initially each
node (i, x) ∈ [d] × [n/d] has as input As [ix, ∗] and Bs [∗, ix] for all s ∈ [k].
for any γ ≥ 0. The function f is a decreasing function of γ, with value a/2 + b + 1/2 when γ = 0
and with limit a + b when γ goes to infinity. The function g is an increasing function of γ, with
value a + 1 when
√ γ = 0 and with limit 2 when γ goes to infinity. Let us choose γ as follows. Since
we assumed kn ≤ m < n2 /k, the equation f (γ) = g(γ) necessarily has a solution. We choose γ
as this solution, i.e., such that
(1 − a) γ = 1 − a + (b − 1) ω(γ).

(8)

Observe that such a choice for γ implies that m ≥ (n/k)γ/ω(γ)+1/2 as we required: Equation (8)
can be rewritten as
(1 − a)γ
1−a
b =1+
−
,
ω(γ)
ω(γ)
which implies
b ≥ (1 − a)



1
γ
+
ω(γ) 2



since ω(γ) ≥ 2. For our choice of γ, the total number of field elements received per node is thus
O(k2/ω(γ) n2−2/ω(γ) ), which gives round complexity
O(k2/ω(γ) n1−2/ω(γ) ),
as claimed, from Lemma 1.
The proof of Theorem 1 now follows easily from Propositions 2 and 3.
√
Proof of Theorem 1. Consider first the case k ≤ n. When kn ≤ m ≤ n2 /k, we use the algorithm
√
of Proposition 3. When m ≥ n2 /k, we use the algorithm of Proposition 2. When 0 ≤ m ≤ kn the
12

claimed
√ upper bound O(k) on the round complexity can be derived from Proposition 2 by taking
m = kn (i.e., by appending rows and columns with zero entries to the input matrices) and γ = 0.
For the case k ≥ n we can simply repeat ⌈k/n⌉ times an algorithm for MM(n, m, n, F), which
gives round complexity

O(k)
if 1 ≤ m ≤ n,
O(km/n) if m ≥ n.

from the analysis of the previous paragraph.

3.2

Application to the distance product

One of the main applications of Theorem 1 is the following result, which will be the key ingredient
for all our results on the all-pairs shortest paths and diameter computation discussed in Section 6.
Theorem 7. For any M ≤ n and m ≤ n, the deterministic round complexity of DIST(n, m, M ) is

√
if 0 ≤ m ≤ M n log m,
 O(M log m)

√
M n log m ≤ m ≤ n2 /(M log m),
O (M log m)2/ω(γ) n1−2/ω(γ)
if

O (mM log m/n)
if n2 /(M log m) ≤ m ≤ n,




M
log m
log M
where γ is the solution of the equation 1 − log
+
−
1
ω(γ).
γ
=
1
−
log n
log n
log n
Let us first give a brief overview of the proof of Theorem 7. The idea is to show that
DIST(n, m, M ) reduces to MM(n, m, k, F) for k ≈ M log m and a well-chosen finite field F, and
then use Theorem 1 to get a factor (M log m)2/ω(γ) , instead of the factor M obtained in a straightforward implementation of the distance product, in the complexity. This reduction is done by first
applying a standard encoding of the distance product into a usual matrix product of matrices with
integer entries of absolute value exp(M ), and then using Fourier transforms to split this latter
matrix product into roughly M log m independent matrix products over a small field.
Proof of Theorem 7. We show below that DIST(n, m, M ) reduces to MM(n, m, k, F) where k =
O(M log m) and |F| = poly(M, log m). The result then follows from Theorem 1.
Let N be any positive integer. We first show how to reduce the multiplication or the addition of
two nonnegative N -bit integers a and b to 2N independent operations (multiplications or additions,
respectively) in a large enough field, using the Fourier transform. Let F be a finite field with
characteristic at least N + 1. Let
ΦN : {0, 1, . . . , 2N −1 } → F[x]/(x2N − 1)
PN −1 i
be the map that maps each N -bit integer c = i=0
ci 2 , with each ci in {0, 1}, to the polynomial
PN −1
i
i=0 ci x . Computing the product ab ∈ Z (resp. the sum a + b ∈ Z) reduces to computing the
product ΦN (a)ΦNP
(b) (resp. the sum ΦN (a) + ΦN (b)) over F[x]/(x2N − 1). Indeed,
P2N −1if ΦiN (a)ΦN (b)
2N −1
is the polynomial i=0
ci xi , with each ci in F, then ab is equal to the sum i=0
ci 2 computed
over the integers (note that the assumption on the characteristic of F is crucial here), and similarly
for the addition. The computation of ΦN (a)ΦN (b) and ΦN (a) + ΦN (b) can be done using the
identities
ΦN (a)ΦN (b) = DF T −1 (DF T (ΦN (a)) · DF T (ΦN (b))),

ΦN (a) + ΦN (b) = DF T

−1

(DF T (ΦN (a)) + DF T (ΦN (b))),
13

(9)
(10)

where DF T : F[x]/(x2N − 1) → F2N is the Fourier transform and where · and the second + represent the coordinate-wise multiplication and addition in F2N , respectively (we refer to [4] for a
detailed presentation of this Fourier transform). In order for the Fourier transform to be defined
we nevertheless need to choose the field F such that it contains a 2N -th primitive root of unity. It
is known (see, e.g., [11]) that for any prime p such that 2N divides p − 1 the finite field F = Zp
contains such a prime root. It is also known ([28, 29], see also [11]) that the least prime p such that
′
2N divides p − 1 is smaller than d(2N )d for some absolute constants d and d′ . By choosing such
a prime p, we obtain a reduction from the computation of ab (resp. a + b) to one coordinate-wise
multiplication (resp. addition) in F2N where |F| = poly(N ). Note that we do not need to discuss
the costs of finding p and the cost of preprocessing/postprocessing operations (such as applying
the Fourier transform and its inverse), since they will have no impact on the round complexity of
the algorithm we design below.
Pm
Let us now consider the task of computing the integer
t=1 at bt given non-negative N -bit
integers a1 , .P
. . , am , b1 , . . . , bm . Similarly to what we just did, this sum can be recovered from the
polynomial m
t=1 ΦN (at )ΦN (bt ), which can be obtained by computing the 2N -dimentional vector
m
X
t=1

DF T (ΦN (at )) · DF T (ΦN (bt ))

(11)

over a finite field F of order polynomial in N and m, and then applying the inverse Fourier transform.
We can now describe our reduction. Let A, B be the matrices with entries in {−M, . . . , M }∪{∞}
of which we want to compute the distance product. We first reduce this distance product to one
usual product of matrices with large entries, using standard techniques [2, 42, 47]. Consider the
n × m matrix A′ by the m × n matrix B ′ defined as:


(m + 1)M −A[i,j] if A[i, j] 6= ∞,
(m + 1)M −B[j,i] if B[j, i] 6= ∞,
′
′
A [i, j] =
B [j, i] =
0
if A[i, j] = ∞,
0
if B[j, i] = ∞,
for all (i, j) ∈ [n] × [m]. It is easy to check (see [47] for a proof) that the entry
A ∗ B[i, j] can be

′
′
recovered easily from entry A B [i, j], for each (i, j) ∈ [n] × [m]. Let N = log2 ((m + 1)2M + 1)
be the number of bits needed to represent the entries of A′ and B ′ , and F be a finite field as in
the previous paragraph. Next, in order to compute A′ B ′ we use the following strategy. For each
(i, j) ∈ [n] × [m], consider the two vectors DF T (ΦN (A′ [i, j])) ∈ F2N and DF T (ΦN (B ′ [j, i])) ∈ F2N .
For convenience write them as ~
pij = (pij [1], . . . , pij [2N ]) and ~qji = (qji [1], . . . , qji [2N ]), respectively.
Now, for any s ∈ [2N ], define the matrix A′s ∈ Fn×m and the matrix Bs′ ∈ Fm×n such that
A′s [i, j] = pij [s] and Bs [j, i] = qji [s] for all (i, j) ∈ [n] × [m]. It follows from the discussion of
the previous paragraph (and in particular Equation (11)) that for each (i, j) ∈ [n] × [n] the entry
′ [i, j]. Since all preprocessing
A′ B ′ [i, j] can be recovered from the entries A′1 B1′ [i, j], . . . , A′2N B2N
and postprocessing steps of this strategy can be performed locally by the nodes of the network
in the congested clique model, this reduces the computation of A′ B ′ to solving one instance of
MM(n, m, 2N, F), with 2N = O(M log m) and |F| = poly(M, m), as claimed.

4

Deterministic Computation of Determinant and Inverse Matrix

In this section we present deterministic algorithms for computing the determinant of a matrix and
the inverse of a matrix in the congested clique model, and prove Theorem 2. Our algorithms can
14

be seen as efficient implementations of the parallel algorithm by Prerarata and Sarwate [37] based
on the Faddeev-Leverrier method.
Let A be an n × n matrix over a field F. Let det(λI − A) = λn + c1 λn−1 + · · · + cn−1 λ + cn be
its characteristic polynomial. The determinant of A is (−1)n cn and, if cn 6= 0, its inverse is
A−1 = −

An−1 + c1 An−2 + · · · + cn−2 A + cn−1 I
.
cn

Define the vector ~c = (c1 , . . . , cn )T ∈ Fn×1 . For any k ∈ [n] let sk denote the trace of the matrix Ak ,
and define the vector ~s = (s1 , . . . , sn )T ∈ Fn×1 . Define the n × n matrix


1
 s1

2


 s2

s
3
1
S=
.
 ..

..
..
..
 .

.
.
.
sn−1 sn−2 sn−3 ... s1 n
It can be easily shown (see, e.g., [9, 37]) that S~c = −~s, which enables us to recover ~c from ~s if S is
invertible. The matrix S is invertible whenever n! 6= 0, which is true in any field of characteristic
zero or in any finite field of characteristic strictly larger than n. The following proposition shows
that the inverse of an invertible triangular matrix can be computed efficiently in the congested
clique model.
Proposition 4. Let F be any field. The deterministic round complexity of INV(n, F), when the
input A is an invertible lower triangular matrix, is O(n1−2/ω ).
Proof. We adapt the standard sequential algorithm for triangular matrix inversion [1, 3]. Let A be
an invertible lower triangular n × n matrix with entries in F. Assume without loss of generality
that n is a power of two. Let us decompose A in four blocks of size n/2 × n/2:


A11
0
A=
.
A21 A22
Observe that both A11 and A22 are invertible lower triangular matrices, and


A−1
0
−1
11
A =
.
−1
A−1
−A−1
22 A21 A11
22
Inverting A thus reduces to inverting two invertible lower triangular matrices of size n/2 × n/2 and
performing two matrix multiplications. We implement this algorithm recursively (and in parallel)
in the congested clique model as follows. The n nodes are partitioned into two groups of size
of n/2: the first group consisting of nodes 1, . . . , n/2 and the second group consisting of nodes
n/2+1, . . . , n. The first group recursively computes A−1
11 and the second group recursively computes
−1
A−1
.
The
important
point
here
is
that
the
computation
of A−1
22
11 and the computation of A22 can
be done independently (i.e., in parallel). The nodes of the second group then in two rounds (using
Lemma 1) distribute appropriately the rows of A−1
22 to the nodes of the first group (who own the
−1
−1
columns of A21 ), so that the nodes of the first group can compute A−1
22 A21 and then −A22 A21 A11 .
−1
The nodes of the first group finally distribute appropriately the rows of −A−1
22 A21 A11 to the nodes
of the second group, in two rounds from Lemma 1.
15

Let RI (n) denote the round complexity of our problem (computing the inverse of an invertible
lower triangular n×n matrix using n nodes), and RM (n) denote the round complexity of computing
the product of two n × n matrices using n nodes (i.e., the problem MM(n, n, 1, F)). The recurrence
relation we obtain is

RI (1) = 0,
RI (n) ≤ RI (n/2) + 2RM (n/2) + 4 for n ≥ 2,
which gives RI (n) = O(n1−2/ω ) since RM (n) = O(n1−2/ω ) from Theorem 1.
We are now ready to give the proof of Theorem 2.
√
Proof of Theorem 2. For convenience we assume that n is a square, and write p = n. If n
√
is not a square we can easily adapt the proof by taking p = ⌈ n⌉. Observe that any integer
a ∈ {0, 1, . . . , n − 1} can be written in a unique way as a = (a1 − 1)p + (a2 − 1) with a1 , a2 ∈ [p].
Below when we write a = (a1 , a2 ) ∈ [n], we mean that a1 and a2 are the two elements in [p] such
that a = (a1 − 1)p + (a2 − 1).
For any ℓ ∈ [n], let Rℓ be the p × n matrix such that the i-th row of Rℓ is the ℓ-th row of A(i−1)p ,
for each i ∈ [p]. Similarly, for any ℓ ∈ [n], let Cℓ be the n × p matrix such that the j-th column of
Cℓ is the ℓ-th column of Aj−1 , for each j ∈ [p]. For each ℓ ∈ [n] define Uℓ = Rℓ Cℓ , which is a p × p
matrix. Observe that, for any k = (k1 , k2 ) ∈ [n], the identity
sk =

n
X

Uℓ [k1 , k2 ]

(12)

ℓ=1

holds. We will use this expression, together with the equation ~c = −S −1~s to compute the determinant in the congested clique model.
In order to compute the inverse of A we then use the following approach. For any (a1 , a2 ) ∈
[p] × [p], define the coefficient ca1 ,a2 ∈ F as follows:

cn−1−(a1 −1)p−(a2 −1) if (a1 , a2 ) 6= (p, p),
ca1 ,a2 =
1
if (a1 , a2 ) = (p, p).
For any a2 ∈ [p], define the n × n matrix Ea2 as follows:
Ea2 =

p
X

ca1 ,a2 A(a1 −1)p .

a1 =1

Note that the following holds whenever cn 6= 0:
Pp
Pp
Pp
Pn−1
(a1 −1)p+(a2 −1)
a
Ea2 Aa2 −1
a2 =1 ca2 ,a1 A
a1 =1
−1
a=0 cn−1−a A
=−
= − a2 =1
.
A =−
cn
cn
cn

(13)

The algorithm for DET(n, F) and INV(n, F) is described in Figure 3. Steps 1 and 7.2 can be
implemented in O(p2/ω n1−2/ω ) rounds from Theorem 1 (or its simplified version in the introduction).
Step 5 can be implemented in O(n1−2/ω ) rounds, again from Theorem 1. At Steps 2, 3 and 6 each
node receives n elements from the field F, so each of these three steps can be implemented in two
rounds from Lemma 1. The other steps (Steps 4, 7.1 and 7.3) do not require any
 communication.
The total round complexity of the algorithm is thus O p2/ω n1−2/ω = O n1−1/ω , as claimed.
16

1. The matrices A(a1 −1)p and Aa2 −1 are computed for all a1 , a2 ∈ [p] using the distributed
algorithm of Theorem 1. At the end of this step node ℓ ∈ [n] has the whole p × n matrix
Rℓ and the whole n × p matrix Cℓ .
2. Node ℓ ∈ [n] locally computes Uℓ , and sends Uℓ [k1 , k2 ] to each node k = (k1 , k2 ) ∈ [n].
3. Node k = (k1 , k2 ) ∈ [n], who received Uℓ [k1 , k2 ] for all ℓ ∈ [n] at the previous step,
locally computes sk using Equation (12). Node k then sends sk to all the nodes.
4. Node ℓ ∈ [n], who received ~s at Step 3, locally constructs S[ℓ, ∗] and S[∗, ℓ].
5. The matrix S −1 is computed using the algorithm of Proposition 4. At the end of this
step, node ℓ ∈ [n] has S −1 [ℓ, ∗] and S −1 [∗, ℓ].
6. Node ℓ ∈ [n] locally computes cℓ from S −1 [ℓ, ∗] and ~s, and sends cℓ to all nodes.
7. The determinant of A is (−1)n cn . If cn = 0 the matrix A is not invertible. Otherwise
the nodes compute A−1 as follows:
7.1 Node ℓ ∈ [n] computes Ea2 [ℓ, ∗] for each a2 ∈ [p] (this can be done locally since ~c
and each row A(a1 −1)p [ℓ, ∗] are known from Steps 6 and 1, respectively).
7.2 The matrices Ea2 Aa2 −1 are computed for all a2 ∈ [p] using the distributed algorithm of Theorem 1 (since, besides Ea2 [ℓ, ∗] obtained at the previous step, each
node ℓ ∈ [n] knows Aa2 −1 [∗, ℓ] from the result of the computation of Step 1). At
the end of this step, node ℓ ∈ [n] has the ℓ-th row and the ℓ-th column of the
matrix Ea2 Aa2 −1 for all a2 ∈ [p].

7.3 Node ℓ ∈ [n] computes locally A−1 [ℓ, ∗] and A−1 [∗, ℓ] using Equation (13).

Figure 3: Distributed algorithm for computing the determinant of an n × n matrix A and computing A−1 if det(A) 6= 0. Initially each node ℓ ∈ [n] has as input A[ℓ, ∗] and A[∗, ℓ].

5

Randomized Algorithms for Algebraic Problems

In this section we present O(n1−2/ω )-round randomized algorithms for computing the determinant,
the rank and for solving linear systems of equations in the congested clique model, and prove
Theorem 3. Our approach is based on Wiedemann’s method [44] and its parallel implementations
[21, 22, 23].
Let A be an n × n matrix over F. The minimal polynomial of A, which we denote minpol(A),
is the monic polynomial g over F of least degree such that g(A) = 0. Let v ∈ Fn×1 and w ∈ F1×n be
any vectors. Consider the sequence wA0 v, wAv, wA2 v, . . . , wAn−1 v consisting of n elements of F.
This sequence is linearly generated over F, and thus also admits a polynomial called the generating
polynomial of the sequence, which we denote minpol(A, v, w). We refer to [16] for the precise
definition of the generating polynomial of such a linearly generated sequence and a description of
efficient algorithms to compute it — in this paper we will just need to know that such a polynomial
exists. Wiedemann [44] showed that with high probability minpol(A, v, w) = minpol(A) when v
and w are chosen at random. We use the following characterization of this property proved by
Kaltofen and Pan [22].
17

Lemma 2. ([22]) Let A be any n × n matrix over F. Let v ∈ Fn×1 and w ∈ F1×n be two vectors
in which each coordinate is chosen uniformly at random from F. Then


2n
.
Pr minpol(A) = minpol(A, v, w) ≥ 1 −
|F|
In general the minimal polynomial of a matrix A is not equal to its characteristic polynomial
charpol(A). Wiedemann [44] nevertheless showed that the characteristic polynomial can be obtained from the minimal polynomial by preconditioning the matrix. Since it will be more convenient
for our purpose to apply a diagonal preconditioner, we will use the following version shown by Chen
et al. [6].
Lemma 3. ([6]) Let A be any n × n matrix over F. Let D be an n × n diagonal matrix where each
diagonal entry is chosen uniformly at random from F \ {0}. Then


n(n − 1)
.
Pr charpol(DA) = minpol(DA) ≥ 1 −
2(|F| − 1)
Kaltofen and Saunders [23] showed that the rank of a matrix can be obtained, with high
probability, from the degree of the minimal polynomial by using another preconditioning of the
matrix. The following lemma follows from the combination of Theorem 1 and Lemma 2 in [23].
Lemma 4. ([23]) Let A be any n × n

1 u2 u3 · · ·

1 u2 · · ·


..
.
U =
1


.
..


matrix over F such that rank(A) < n. Let


un
1
un−1 
 v2
1


.. 

v3
v2
1
. 
, V = 
 ..
.

.. ...
 .
u2 
vn vn−1 · · · v2 1
1









be two n × n unit (upper and lower, respectively) triangular random Toepliz matrices. Let D be an
n × n diagonal matrix where each diagonal entry is chosen uniformly at random from F. Then


n(3n + 1)
.
Pr rank(A) = deg(minpol(U AV D)) − 1 ≥ 1 −
2|F|
We are now ready to prove Theorem 3.
Proof of Theorem 3. We first show how to compute efficiently, in the congested clique model, the
sequence Ã0 u, Ãu, Ã2 u, . . .,Ãn−1 u given an arbitrary matrix Ã ∈ Fn×n and an arbitrary vector
u ∈ Fn×1 . For convenience assume that n is a power of two (otherwise we can simply add zero rows
and columns to Ã and zero entries to u), and write n = 2k for some positive integer k. For each
i ∈ {0, . . . , k}, define the n × n matrix
i

M (i) = [u|Ãu| · · · |Ã2 −1 u|0| · · · |0],
i −1

obtained by concatenating the vectors u, . . . , Ã2
each i ∈ {0, . . . , k − 1}, define the n × n matrix

u and then adding 2k − 2i zero columns. For
i

N (i) = [0| · · · |0|u|Ãu| · · · |Ã2 −1 u|0| · · · |0],
18

i

obtained by concatenating the vectors u, . . . , Ã2 −1 u, adding 2i zero columns on the left and 2k −2i+1
zero columns on the right. Observe that, for any i ∈ {0, . . . , k − 1}, the equality
i

M (i+1) = M (i) + Ã2 N (i)
i−1

i

holds. Moreover, for any i ∈ {1, . . . , k − 1}, the matrix Ã2 can be obtained by multiplying Ã2 by
itself. This enables us to compute the n vectors Ã0 u, Ãu, Ã2 u, . . . , Ãn−1 u using only 2k − 1 matrix
multiplications. We describe in Figure 4 the implementation of this approach in the congested
clique model, which uses O(kn1−2/ω ) = O(n1−2/ω log n) rounds.
input: node ℓ ∈ [n] has Ã[ℓ, ∗], Ã[∗, ℓ] and u
output: node ℓ ∈ [n] has M (k) [∗, ℓ] = Ãℓ−1 u
1. M (0) ← [u|0| · · · |0]
(Node ℓ ∈ [n] locally constructs M (0) [ℓ, ∗] and M (0) [∗, ℓ])
2. N (0) ← [0|u|0| · · · |0]
(Node ℓ ∈ [n] locally constructs N (0) [ℓ, ∗] and N (0) [∗, ℓ])
3. For i from 0 to k − 1 the nodes do:
i

3.1 The nodes compute Ã2 N (i) using the algorithm of Theorem 1: after the computai
i
tion node ℓ ∈ [n] has Ã2 N (i) [ℓ, ∗] and Ã2 N (i) [∗, ℓ].

3.2 The nodes locally compute M (i+1) : node ℓ ∈ [n] computes M (i+1) [ℓ, ∗] = M (i) [ℓ, ∗]+
i
i
Ã2 N (i) [ℓ, ∗] and M (i) [∗, ℓ] = M (i) [∗, ℓ] + Ã2 N (i) [∗, ℓ].
i+1

3.3 If i 6= k − 1 the nodes compute Ã2

i

i

= Ã2 Ã2 using the algorithm of Theorem 1.

Figure 4: Distributed randomized algorithm for computing the sequence Ã0 u, Ãu, Ã2 u, . . . , Ãn−1 u
given a matrix Ã ∈ Fn×n and a vector u ∈ Fn×1 . Here n is a power of two, written n = 2k .
We now describe a O(n1−2/ω log n)-round algorithm in the congested clique model that computes, with high probability, the minimal polynomial minpol(A) of an arbitrary matrix A ∈ Fn×n .
More precisely, the matrix A is initially distributed among the n nodes of the network (node ℓ ∈ [n]
receives as input A[ℓ, ∗] and A[∗, ℓ]) and at the end of the computation we would like a designated
node of the network (say, node 1) to have the polynomial minpol(A). The algorithm is as follows.
First, a designated node (say, node 1 again) takes two random vectors v, w as in Lemma 2. This
node then sends v, w to all the nodes of the network in four rounds of communication using the
scheme of Lemma 1. Then the nodes of the network apply the algorithm of Figure 4 with Ã = A
and u = v. After this, each node ℓ ∈ [n] owns Aℓ−1 v, and can then compute locally the field
element wAℓ−1 v. All nodes then sends their result to node 1 using one round of communication.
Node 1 finally computes locally the polynomial minpol(A, v, w). The complexity of this algorithm
is clearly O(n1−2/ω log n) rounds. The correctness follows from Lemma 2, which guarantees that
minpol(A) = minpol(A, v, w) with probability at least 1 − 2n/|F|.
Our O(n1−2/ω log n)-round algorithm for INV(n, F) (i.e., for solving the linear system Ax = b
where A is invertible) in the congested clique model is as follows. The nodes of the network first use
the algorithm of the previous paragraph, so that node 1 obtains with high probability minpol(A).
Let us write minpol(A) as m0 + m1 λ + · · · + mn λn , with mn = 1. From the definition of the
19

minimal polynomial, we have
x=

m1 b + m2 Ab + · · · + mn An−1 b
.
−m0

(14)

Node 1 then sends the two field elements m0 and mℓ to node ℓ, for each ℓ ∈ {1, . . . , n}, in two
rounds. The nodes of the network use the O(n1−2/ω log n)-round algorithm of Figure 4 with u = b
and Ã = A, so that each node ℓ ∈ [n] owns Aℓ−1 b at the end of the computation. Each node ℓ ∈ [n]
mℓ ℓ−1
then locally computes − m
A b, and sends the ℓ′ -th coordinate of this vector to node ℓ′ , for each
0
ℓ′ ∈ [n]. This can be done in two rounds. Node ℓ ∈ [n] then adds the n elements he receives, which
gives x[ℓ] from Equation (14).
We now describe our O(n1−2/ω log n)-algorithm for DET(n, F). First, a designated node (say,
node 1) takes a random diagonal matrix D as in Lemma 3. This node then sends D to all the
nodes of the network using two rounds of communication (using the scheme of Lemma 1). Each
node ℓ ∈ [n] of the network then constructs DA[ℓ, ∗] and DA[∗, ℓ]. The nodes of the network
then apply the above algorithm computing the minimal polynomial, so that Node 1 obtains with
high probability minpol(DA). Let m0 denote the constant term of minpol(DA). Note that the
determinant of DA is (−1)n m0 , from Lemma 3, and thus the determinant of A is
(−1)n m0
Qn
.
i=1 D[i, i]

Node 1 sends this value all the nodes of the network in one round of communication.
Finally, we present our algorithm for Rank(n, F). First, we can check with high probability
whether rank(A) = n by computing det(A) using the algorithm described in the previous paragraph.
Therefore we assume below that rank(A) < n, and compute the rank as follows. A designated node
(say, node 1) takes three random matrices U, V, D as in Lemma 4, and sends the three matrices to
all the nodes of the network in six rounds using the scheme of Lemma 1 (note that each matrix is
described by at most n coefficients). The nodes of the network then apply the O(n1−2/ω )-round
algorithm of Theorem 1 three times to compute U AV D. They then use the O(n1−2/ω log n)-round
algorithm computing the minimal polynomial, so that Node 1 obtains minpol(U AV D). Node 1
locally computes deg(minpol(U AV D)) − 1 and sends this value to all the nodes of the network in
one round. The correctness of this algorithm is guaranteed by Lemma 4.

6

Applications to Graph-Theoretic Problems

In this section we consider applications of our results to graph-theoretic problems in the congested
clique model.

6.1

The All Pair Shortest Paths problem

The All-Pairs Shortest Paths problem (APSP) asks, given a weighted graph G = (V, E), to compute
the shortest path between u and v for all pairs of vertices (u, v) ∈ V ×V . For simplicity, but without
significant loss of generality, we will assume that the weights are O(log n)-bit integers. When the
graph G is undirected, the definition of the APSP requires the weights to be nonnegative (otherwise
there would be negative cycles). When the graph G is directed negative weights are allowed but it is
implicitly required that the graph has no non-negative cycle. We say that the graph is unweighted
20

if the only allowed weight is one. In this subsection the term “adjacency matrix of G” refers to the
|V | × |V | matrix in which the entry in the i-th row and j-th column is the weight of the edge from
the i-th node to the j-th node of the graph if these two nodes are connected and ∞ otherwise.
Let us first describe very briefly the main results concerning the complexity of the APSP in the
centralized setting. For undirected unweighted graphs, Seidel [40] showed that the APSP reduces
to computing the powers of the adjacency matrix (seen as a matrix over the integers) of the graph,
and can thus be solved in Õ(nω ) time. For all other cases, including directed graphs and undirected
graphs with arbitrary weights, the standard algebraic way of solving the APSP is to compute the
powers of the distance product of the adjacency matrix of the graph. This distance product of
an n × m matrix A by an m × n matrix B can be trivially solved in time O(smn2 ), where s
denotes the number of bits needed to represent each entry of A and B, which gives a Õ(n3 )-time
algorithm for the APSP. Despite much research (including recent exciting developments [45]), no
significantly better algorithm is known for computing the distance product or solving the general
APSP. Faster algorithms for computing the distance product can be nevertheless designed when the
entries of A and B are small integers, i.e., the entries are in {−M, . . . , −1, 0, 1, . . . , M } ∪ {∞} for
some integer M . As already mentioned in the proof of Theorem 7, Alon et al. [2] and Takaoka [42]
(for the square case) and then Zwick [47] (for the rectangular case) showed that C can be recovered
easily from the standard matrix product of the n × m matrix A′ by the m × n matrix B ′ where


(m + 1)M −A[i,j] if A[i, j] 6= ∞,
(m + 1)M −B[j,i] if B[j, i] 6= ∞,
A′ [i, j] =
B ′ [j, i] =
0
if A[i, j] = ∞,
0
if B[j, i] = ∞,
for all (i, j) ∈ [n] × [m]. This implies in particular that the distance product can be computed in
Õ(M nω(log m/ log n) ) time, and in particular in Õ(M nω ) time when m = n. Shoshan and Zwick [41]
used this technique (for the square case) to obtain a Õ(M nω )-time algorithm for the APSP in
undirected graphs with weights in {0, . . . , M }. Zwick used this technique (for the rectangular case)
to construct an algorithm for the directed case. He obtained in particular time complexity O(n2.58 ),
which has been improved to O(n2.54 ) using the best known upper bound on the exponent of rectangular matrix multiplication [24], when M is constant (and in particular for directed unweighted
graphs).
Censor-Hillel et al. [5] showed how to adapt Seidel’s method [40] to solve the APSP over undirected unweighted graphs in Õ(n1−2/ω ) rounds. They also observed that the centralized matrix
algorithms for the distance product discussed above can be implemented in the congested clique
model, solving DIST(n, n, M ) in O(min{n1/3 log n, M n1−2/ω }) rounds. While not explicitly stated
in [5], this result gives a O(M n1−2/ω )-round algorithm for the APSP in undirected graphs with
weights in {0, 1, . . . , M }, by observing that the reduction given in [41] from such instances of APSP
to the computation of the distance product can be implemented efficiently in the congested clique
model. Our improved upper bound (Theorem 4 stated in the introduction) follows directly from
our improved algorithm for the computation of the distance product in the congested clique model
(Theorem 7).
We now consider the APSP in directed graphs with small integer weights and prove Theorem 5.
Besides the new bounds of Theorem 7, we will also use another upper bound on the round complexity
of DIST(n, m, M ), which is better for large values of M . This is the bound obtained from Theorem 1
for the choice ω(ℓ) = 2 + ℓ corresponding to the implementation of the trivial matrix multiplication
algorithm (which works over any semiring, see Section 2) in the congested clique model. We state
this bound in the following proposition.
21

Proposition 5. The round complexity of DIST(n, m, M ) is

√
O(log M )
if 0 ≤ m ≤ n,
√
O(m2/3 n−1/3 log M ) if m ≥ n.
We are now ready to prove Theorem 5.
Proof of Theorem 5. Let A be the adjacency matrix of the graph G = (V, E). The centralized
algorithm by Zwick [47] works as follows. The algorithm performs ⌈log3/2 n⌉ iteration, while maintaining an n × n matrix F initially set to F = A. In the k-th iteration, it sets s = (3/2)k , and
takes a set S ⊆ V of O((n log n)/s) vertices chosen uniformly at random from V . The algorithm
then construct the submatrix of size |S| × n of F , denoted F [S, ∗], consisting of the rows corresponding to the vertices in S, and the submatrix of size n × |S| of F , denoted F [∗, S], consisting
of the columns corresponding to vertices in S. It then puts a cap of sM on the absolute values
of the entries of F [S, ∗] and F [∗, S]. The last step of the iteration is to compute the distance
product F ′ = F [∗, S] ∗ F [S, ∗] and, for each (i, j) ∈ [n × n], replace the (i, j) entry of F by F ′ [i, j] if
F ′ [i, j] < F [i, j]. It can be shown that after the last iteration the entry F [i, j] is the length of the
shortest path between the i-th node and the j-th node of the graph, for all (i, j) ∈ [n × n], if the
graph has no negative cycle.
This centralized algorithm can be implemented easily in the congested clique model. The only
part that requires communication between the nodes is the computation of the distance product:
at step i the nodes need to compute the distance product of a n × m matrix by a m × n matrix
with entries of absolute values bounded by ⌈sM ⌉ with m = O((n log n)/s) and s = (3/2)i . We have
two strategies to compute the distance product, the algorithm of Proposition 5 and the algorithm
of Theorem 7. Since there are only O(log n) iterations, the total round complexity is
o

n
(15)
Õ min 1 + (n/s)2/3 n−1/3 , s + s2/ω(γ) n1−2/ω(γ) ,
for the value
of s the maximizes this expression, where γ denotes the solution of the equation
log(n/s)
log s
log s 
γ
=
1 − log
1 − log
n
n +
log n − 1 ω(γ). As in the analysis for the centralized setting given
in [47], the left part of (15) is a decreasing function of s, while the right part is an increasing
function of s. Using the best known upper bound on ω(γ) from [24] (see also Figure 5), we can
upper bound the total round complexity by O(n0.2096 ).
Note that the above algorithm only computes the lengths of the shortest paths. As in Zwick’s
centralized algorithm, the shortest paths can be constructed by using exactly the same strategy,
but constructing a matrix of witnesses whenever a distance product is computed (as described in
Section 3 of [47]), which can be done with the same round complexity.
While a result similar to Theorem 5 can be obtained when M is not a constant, by using exactly
the same algorithm but keeping the value M in Equation (15), in this case it is complicated to
express the result of the numerical optimization in a closed form, so we omit this generalization. An
interesting open question is whether the algorithm of Theorem 5 can be derandomized. While Zwick
showed that this can be done in the centralized setting by introducing the concept of bridging sets, it
does not seem that the algorithm proposed in [47] for constructing bridging sets can be implemented
efficiently in the congested clique model.

22

n1

Value 1 + (n/s)2/3 n−1/3
Value s + s2/ω(γ) n1−2/ω(γ)

n1/3
n0.2095...
n0.1572
n0
n0

n0.1856...

n1/3

n1/2
Value of s

n1

Figure 5: Values of the two parts of Equation (15).

6.2

Diameter computation

Since computing the diameter of a graph trivially reduces to the APSP problem, we immediately
obtain the following result.
Corollary 1. In the congested clique model, the deterministic round complexity of diameter computation in an undirected graph of n vertices with integer weights in {0, . . . , M }, where M is an
integer such that M ≤ n, is Õ(M 2/ω n1−2/ω ).
The same reduction can be used to obtain a randomized algorithm for computing the diameter
of directed graphs with constant integer weights in O(n0.2096 ) rounds, via Theorem 5. This round
complexity can nevertheless be improved. In the centralized setting it is known that over directed
graphs with integer weights in {−M, . . . , M }, but without cycles of negative weights, the diameter
can be computed in O(M nω ) time, i.e., faster than the best known centralized algorithm for the
corresponding APSP problem. This is a folklore result based on the reductions to the distance
product developed in [41, 47] (see also [10]). A close inspection of this approach shows that it can
be implemented efficiently in the congested clique model, and Theorem 7 thus implies that the
diameter can be computed in Õ(M 2/ω n1−2/ω ) rounds in direct graphs (without cycles of negative
weights) with integer weights in {−M, . . . , M } as well.

6.3

Maximum matchings

Let G = (V, E) be a simple graph (i.e., an undirected and unweighted graph with no loops or
multiple edges), and write V = {v1 , . . . , vn }. The Tutte matrix of G is the n × n symbolic matrix

23

A such that


 xij
A[i, j] =
−xij

0

if i > j and {vi , vj } ∈ E,
if i < j and {vi , vj } ∈ E,
otherwise,

for any (i, j) ∈ [n] × [n]. Let ν(G) denote the number of edges in a maximum matching of G.
Lovász [31] showed that rank(A) = 2ν(G). Rabin and Vazirani [38] observed that this equality
remains true over any field. As mentioned in [38], this gives a simple randomized algorithm for
computing rank(A), and thus ν(G), based on Schwartz-Zippel lemma [39, 46]: take a prime p =
Θ(n4 ), substitute the variables xij by random elements from the finite field Zp to obtain a matrix Â
over Zp , and compute the rank of Â over Zp (which will be equal to rank(A) with high probability).
This approach can clearly be implemented efficiently in the congested clique mode using the rank
algorithm of Theorem 3, giving the following result.
Theorem 8. The randomized round complexity of computing the number of edges in a maximum
matching of a simple graph is O(n1−2/ω log n).
Suppose that the graph G has a perfect matching (i.e., n is even and ν(G) = n/2). We say that
an edge of G is allowed if it is contained in a least one perfect matching. Rabin and Vazirani [38]
further showed that with high probability the following property holds for all edges {i, j} of G: the
edge {i, j} is allowed if and only if Â−1 [i, j] 6= 0. The set of allowed edges can thus be obtained
from the inverse of the matrix Â, which can be done in O(n1−1/ω ) rounds in the congested clique
model using the algorithm of Theorem 2.
An interesting open question is whether finding a perfect matching can be done with the same
complexity in the congested clique model. While the best centralized algorithms can find a maximum matching with essentially the same complexity as matrix multiplication [33], they are based
on sequential variants of the Gaussian decomposition (e.g., computation of the LUP decomposition)
that do not appear to be implementable in parallel.

6.4

Computing the Gallai-Edmonds decomposition of a graph

Let G = (V, E) be a simple graph. We say that a vertex v ∈ V is critical if it appears in at least
one maximum matching, otherwise we say that v is non-critical. Let D(G) ⊆ V denote the set
of non-critical vertices, K(G) be the set of vertices in V \ D(G) that are adjacent to vertices in
D(G), and define C(G) = V \ (D(G) ∩ K(G)). Gallai [15] and Edmonds [14] showed that the triple
(D(G), K(G), C(G)), called the Gallai-Edmonds decomposition of the graph, gives fundamental
information about the structure of the graph, and in particular about its matchings (see, e.g., [32] for
a detailed presentation of this theorem). Cheriyan [7] presented efficient algorithms for computing
the Gallai-Edmonds decomposition. We adapt this algorithm to the congested clique model to
obtain the following result.
Theorem 9. The randomized round complexity of computing the Gallai-Edmonds decomposition
of a simple graph is O(n1−1/ω ).
Proof. We will show how all the nodes of the network can obtain the set of non-critical vertices
D(G) in Õ(n1−1/ω ) rounds. Note that K(G) and C(G) can then be computed (and distributed to
all the nodes) in a constant number of rounds using the scheme of Lemma 1.
The strategy used in [7] to compute the set of non-critical vertices D(G) in the centralized
setting is as follows. Take a prime p = Θ(n3 ) and substitute the variables xij in the Tutte matrix
24

of G by random elements from the finite field F = Zp . Let Â denote the matrix obtained. For any
i ∈ [n], let ei ∈ F1×n be the row vector with coordinate 1 at position i and coordinate zero at all
other positions. Cheriyan [7] showed that with large probability the following property holds for
all i ∈ [n]: the vertex vi is non-critical if and only if


Â
rank
> rank(Â).
(16)
ei
 
Â
Here
denotes the (n + 1) × n matrix obtained by appending the row ei at the bottom of Â.
ei
The set D(G) can be computed by checking if Equation (16) holds for each i ∈ [n], but this is not
efficient enough. Observe that Equation (16) holds if and only if ei is not in the subspace S spanned
by the row vectors of Â. Let M ∈ Fn×(n−rank(Â)) be the matrix representation of a basis for the right
null space of Â (i.e., each column of M is a basis vector of the vector space S ⊥ = {y ∈ Fn | Ây = 0}).
Observe that for any row vector u we have uM = 0 if and only if u ∈ (S ⊥ )⊥ = S. Equation (16)
then holds if and only if ei M 6= 0. In order to compute ei M for all i ∈ [n], we simply need to
compute the product of the n × n identity matrix In by the matrix Â, and check which rows of the
product contain at least one non-zero entry.
In the congested clique model this strategy can be implemented in O(n1−2/ω ) rounds assuming
that the matrix M is available (and distributed among the nodes). We now explain how to construct
this matrix using the ideas from [21, 23]. Let r denote the rank of A. Let U, V be two triangular
random Toeplitz matrices as in Lemma 4, and write N = U ÂV . Decompose N as follows:


N11 N12
,
N=
N21 N22
where N11 ∈ Fr×r , N12 ∈ Fr×(n−r) , N21 ∈ F(n−r)×r and N22 ∈ F(n−r)×(n−r) . Theorem 2 from [23]
and the analysis of Section 5 in [21] shows that, with probability at least 1 − r(r + 1)/|F| on the
choice of U and V , the submatrix N11 is non-singular and the columns of the n × (n − r) matrix

  r×(n−r) 
−1
Ir
−N11
N12
0
M =V
.
In−r
0(n−r)×r
In−r
form a basis of the right null space of Â. The matrix M can thus be computed with high probability
in O(n1−1/ω ) rounds by using the algorithm of Theorem 2 for computing the inverse and the
algorithm for matrix multiplication of Section 3.
As already mentioned, the Gallai-Edmonds decomposition has many applications. In particular, as pointed out by Cheriyan [7], an algorithm computing the Gallai-Edmonds decomposition
immediately yields an algorithm computing a minimum vertex cover in a bipartite graph. Cheriyan
also presented other graph-theoretic problems that can be solved using variants of his approach for
computing the Gallai-Edmonds decomposition: finding the canonical partition of an elementary
graph, computing the maximum number of vertex disjoint paths between two subsets of vertices of
a graph, and computing a minimal separator between two subsets of vertices of a graph. A close
inspection of these variants (Sections 3.3 and 4 in [7]) shows that they can also be implemented
efficiently in the congested clique model, giving again algorithms with round complexity O(n1−1/ω ).

25

Acknowkedgments
The author is grateful to Arne Storjohann for precious help concerning the computation of the
determinant and to anonymous reviewers for their comments. This work is supported by the
Grant-in-Aid for Young Scientists (A) No. 16H05853, the Grant-in-Aid for Scientific Research (A)
No. 16H01705, and the Grant-in-Aid for Scientific Research on Innovative Areas No. 24106009 of
the Japan Society for the Promotion of Science and the Ministry of Education, Culture, Sports,
Science and Technology in Japan.

References
[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The design and analysis of computer
algorithms. Addison-Wesley Publishing Company, 1974.
[2] Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path
problem. Journal of Computer and System Sciences, 54(2):255–262, 1997.
[3] James R. Bunch and John E. Hopcroft. Factorization and inversion by fast matrix multiplication. Mathematics of Computation, 28(125):231–236, 1974.
[4] Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity
theory. Springer, 1997.
[5] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka
Suomela. Algebraic methods in the congested clique. In Proceedings of the 34th Symposium
on Principles of Distributed Computing, pages 143–152, 2015.
[6] Li Chen, Wayne Eberly, Erich Kaltofen, B. David Saunders, William J. Turner, and Gilles
Villard. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its
Applications, 343-344:119–146, 2002.
[7] Joseph Cheriyan. Randomized Õ(M (|V |)) algorithms for problems in matching theory. SIAM
Journal on Computing, 26(6):1635–1669, 1997.
[8] Jeff I. Chu and Georg Schnitger. Communication complexity of matrix computation over finite
fields. Mathematical Systems Theory, 28(3):215–228, 1995.
[9] Laszlo Csanky. Fast parallel matrix inversion algorithms. In Proceedings of the 16th Annual
Symposium on Foundations of Computer Science, pages 11–12, 1975.
[10] Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of BaurStrassen’s theorem: Shortest cycles, diameter and matchings. In 53rd Annual IEEE Symposium
on Foundations of Computer Science, pages 531–540, 2012.
[11] Anindya De, Piyush P. Kurur, Chandan Saha, and Ramprasad Saptharishi. Fast integer
multiplication using modular arithmetic. SIAM Journal on Computing, 42(2):685–699, 2013.
[12] Danny Dolev, Christoph Lenzen, and Shir Peled. “Tri, Tri Again”: Finding triangles and
small subgraphs in a distributed setting - (extended abstract). In Proceedings of the 26th
International Symposium on Distributed Computing, pages 195–209, 2012.
26

[13] Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique
model. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages
367–376, 2014.
[14] Jack Edmonds. Paths, tree and flowers. Canadian Journal of Mathematics, 17:449–467, 1965.
[15] Tibor Gallai. Maximale Systeme unabhängiger Kanten. Publications of the Mathematical
Institute of the Hungarian Academy of Sciences, 9:401–413, 1964.
[16] Joachim von zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge University
Press, 2003.
[17] James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and
Michele Scquizzato. Toward optimal bounds in the congested clique: Graph connectivity and
MST. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages
91–100, 2015.
[18] James W. Hegeman and Sriram V. Pemmaraju. Lessons from the congested clique applied
to MapReduce. In Proceedings of the 21st International Colloqium on Structural Information
and Communication Complexity, pages 149–164, 2014.
[19] James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh. Near-constant-time distributed algorithms on a congested clique. In Proceedings of the 28th International Symposium
on Distributed Computing, pages 514–530, 2014.
[20] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almosttight distributed algorithm for approximating single-source shortest paths. In Proceedings of
the 48th Annual ACM Symposium on Theory of Computing, pages 489–498, 2016.
[21] Erich Kaltofen and Victor Y. Pan. Processor efficient parallel solution of linear systems over
an abstract field. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms
and Architectures, pages 180–191, 1991.
[22] Erich Kaltofen and Victor Y. Pan. Processor-efficient parallel solution of linear systems II:
the positive characteristic and singular cases (extended abstract). In Proceedings of the 33rd
Annual Symposium on Foundations of Computer Science, pages 714–723, 1992.
[23] Erich Kaltofen and B. David Saunders. On Wiedemann’s method of solving sparse linear
systems. In Proceedings of the 9th International Symposium on Applied Algebra, Algebraic
Algorithms and Error-Correcting Codes, pages 29–38, 1991.
[24] François Le Gall. Faster algorithms for rectangular matrix multiplication. In Proceedings of
the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 514–523, 2012.
[25] François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th
International Symposium on Symbolic and Algebraic Computation, pages 296–303, 2014.
[26] Christoph Lenzen. Optimal deterministic routing and sorting on the congested clique. In
Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 42–50,
2013.
27

[27] Christoph Lenzen and Roger Wattenhofer. Tight bounds for parallel randomized load balancing: extended abstract. In Proceedings of the 43rd ACM Symposium on Theory of Computing,
pages 11–20, 2011.
[28] Yuri Vladimirovich Linnik. On the least prime in an arithmetic progression I. The basic
theorem. Rec. Math. [Mat. Sbornik] N.S., 15(57):139 – 178, 1944.
[29] Yuri Vladimirovich Linnik. On the least prime in an arithmetic progression II. The DeuringHeilbronn phenomenon. Rec. Math. [Mat. Sbornik] N.S., 15(57):347 – 368, 1944.
[30] Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg. MST construction in o(log log n)
communication rounds. In Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 94–100, 2003.
[31] László Lovász. On determinants, matchings, and random algorithms. In Fundamentals of
Computation Theory, pages 565–574, 1979.
[32] László Lovász and Michael D. Plummer. Matching Theory. American Mathematical Society,
2009.
[33] Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In Proceedings of the 45th Symposium on Foundations of Computer Science, pages 248–255, 2004.
[34] Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In
Proceedings of the 46th Symposium on Theory of Computing, pages 565–573, 2014.
[35] Boaz Patt-Shamir and Marat Teplitsky. The round complexity of distributed sorting: extended
abstract. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed
Computing, pages 249–256, 2011.
[36] David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and
Applied Mathematics, 2000.
[37] Franco P. Preparata and Dilip V. Sarwate. An improved parallel processor bound in fast
matrix inversion. Information Processing Letters, 7(3):148–150, 1978.
[38] Michael O. Rabin and Vijay V. Vazirani. Maximum matchings in general graphs through
randomization. Journal of Algorithms, 10(4):557–567, 1989.
[39] Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities.
Journal of the ACM, 27(4):701–717, 1980.
[40] Raimund Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs.
Journal of Computer and System Sciences, 51(3):400–403, 1995.
[41] Avi Shoshan and Uri Zwick. All pairs shortest paths in undirected graphs with integer weights.
In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages
605–615, 1999.
[42] Tadao Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica,
20(3):309–318, 1998.
28

[43] Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In
Proceedings of the 44th Symposium on Theory of Computing, pages 887–898, 2012.
[44] Douglas H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions
on Information Theory, 32(1):54–62, 1986.
[45] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the
46th Symposium on Theory of Computing, pages 664–673, 2014.
[46] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, pages 216–226, 1979.
[47] Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication.
Journal of the ACM, 49(3):289–317, 2002.

29

