Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique

我们提出了一种协议，用于在拥挤的团中求解两个 $n\times b$ 布尔矩阵的布尔矩阵乘积，该协议适用于第一个矩阵的行或第二个矩阵的列在 $\{0,1\}^n$ 空间中高度聚集的情况。在高概率下，它在拥挤的团中使用 $\tilde{O}\left(\sqrt {\frac M n+1}\right)$ 轮，其中 $n$ 为节点数，$M$ 是第一个输入矩阵的行的最小生成树（MST）的成本和第二个输入矩阵的列的 MST 的成本在 Hamming 空间 $\{0,1\}^n$ 中的最小值。我们协议中的一个关键步骤是计算在 $\{0,1\}^n$ 空间中的 $n$ 个点的近似最小生成树。我们提供了一个协议来解决这个问题（本身很有趣），基于 Hamming 空间中的已知随机降维技术。高概率下，它在拥挤的团中使用 $O(\log^3 n)$ 轮，构建了 $n$ 个点在 Hamming 空间 $\{0,1\}^n$ 中的 MST 的 $O(1)$-近似因子。

论文提出了一种在拥挤的完全图上解决高度聚类的布尔矩阵乘法问题的协议，重点解决了第一个输入矩阵的行或第二个输入矩阵的列在n维哈明空间中高度聚集的情况。同时，提供了一个解决在哈明空间中计算n个点的近似最小生成树问题的协议。

论文中提出的关键思路是通过哈明空间中的降维技术，计算n个点的近似最小生成树，然后利用这个结果来解决高度聚集的布尔矩阵乘法问题。

论文在拥挤的完全图上提出了一种解决高度聚集的布尔矩阵乘法问题的协议，并提供了一个解决在哈明空间中计算n个点的近似最小生成树问题的协议。同时，该协议在计算最小生成树时只需要O(log^3 n)轮，并且能够构造出一个O(1)因子的近似最小生成树。

近期的相关研究包括：《A Distributed Algorithm for Minimum Spanning Trees》、《Fast Distributed Algorithms for Computing Low-Diameter Decompositions》等。