Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
<|reference_start|>Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique: We present a protocol for the Boolean matrix product of two $n\times b$ 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 $\tilde{O}\left(\sqrt {\frac M n+1}\right)$ 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(\log^3 n)$ rounds on the congested clique with $n$ nodes.<|reference_end|>
@article{lingas2024boolean,
    title={Boolean Matrix Multiplication for Highly Clustered Data on the Congested
  Clique},
    author={Andrzej Lingas},
    journal={arXiv preprint arXiv:2405.16103},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.16103},
    primaryClass={cs.DS cs.DC}
}