@inproceedings{a92e984ec2674f87af683d897c1ee725,
title = "Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique",
abstract = "We present a protocol for the Boolean matrix product of two n×n Boolean matrices on the congested clique designed for the situation when the rows of the first matrix or the columns of the second matrix are highly clustered in the space \{0,1\}n. With high probability (w.h.p), it uses O\textasciitilde{}Mn+1 rounds on the congested clique with n nodes, where M is the minimum of the cost of a minimum spanning tree (MST) of the rows of the first input matrix and the cost of an MST of the columns of the second input matrix in the Hamming space \{0,1\}n. A key step in our protocol is the computation of an approximate minimum spanning tree of a set of n points in the space \{0,1\}n. We provide a protocol for this problem (of interest in its own rights) based on a known randomized technique of dimension reduction in Hamming spaces. W.h.p., it constructs an O(1)-factor approximation of an MST of n points in the Hamming space \{0,1\}n using O(log3n) rounds on the congested clique with n nodes.",
keywords = "Boolean matrix product, congested clique, Hamming space, minimum spanning tree (MST)",
author = "Andrzej Lingas",
year = "2024",
doi = "10.1007/978-3-031-69583-4\_4",
language = "English",
isbn = "9783031695827",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media B.V.",
pages = "45--58",
editor = "Jesus Carretero and Javier Garcia-Blas and Sameer Shende and Ivona Brandic and Katzalin Olcoz and Martin Schreiber",
booktitle = "Euro-Par 2024",
address = "United States",
note = "30th International Conference on Parallel and Distributed Computing, Euro-Par 2024 ; Conference date: 26-08-2024 Through 30-08-2024",
}