The Communication Complexity of Set Intersection and Multiple Equality Testing
Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang · SIAM Journal on Computing · 2021
In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets of size $k$ and EqualityTesting between vectors of length $k$. Sağlam and Tardos [ Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687] and Brody et al. [ Algorithmica, 76 (2016), pp. 796--845] showed that for these types of problems, one can achieve optimal communication volume of $O(k)$ bits, with a randomized protocol that takes $O(\log^* k)$ rounds. They also proved that this is one point along the optimal round-communication trade-off curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability $p_{{err}}$, which we write $2^{-E}$. It is straightforward to show that protocols for SetIntersection or EqualityTesting need to send at least $\Omega(k + E)$ bits, regardless of the number of rounds. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k + E)$ communication and $O(\log^* k)$ rounds? In this paper we prove that there is no universally optimal algorithm, and we complement the existing round-communication trade-offs [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845] with a new trade-off between rounds, communication, and probability of error. In particular, any protocol for solving multiple EqualityTesting in $r$ rounds with failure probability $p_{{err}} = 2^{-E}$ has communication volume $\Omega(Ek^{1/r})$. We present several algorithms for multiple EqualityTesting (and its variants) that match or nearly match our lower bound and the lower bound of [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845]. Lower bounds on EqualityTesting extend to SetIntersection for every $r, k,$ and $p_{{err}}$ (which is trivial); in the reverse direction, we prove that upper bounds on EqualityTesting for $r, k, p_{{err}}$ imply similar upper bounds on SetIntersection with parameters $r+1, k,$ and $p_{{err}}$. Our original motivation for considering $p_{{err}}$ as an independent parameter came from the problem of enumerating triangles in distributed (${CONGEST}$) networks having maximum degree $\Delta$. We prove that this problem can be solved in $O(\Delta/\log n + \log\log \Delta)$ time with high probability $1-1/{poly}(n)$. This beats the trivial (deterministic) $O(\Delta)$-time algorithm and is superior to the $\tilde{O}(n^{1/3})$ algorithm of [Y. Chang, S. Pettie, and H. Zhang, Proceedings of the 30 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 821--840; Y. Chang and T. Saranurak, Proceedings of the ACM Symposium on Principles of Distributed Computing, 2019, pp. 66--73] when $\Delta=\tilde{O}(n^{1/3})$.