In this paper we explore fundamental problems in randomized communication complexity such as computing Set Intersection on sets of size $k$ and Equality Testing between vectors of length $k$. Sa\u{ g}lam and Tardos and Brody et al. 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. Aside from rounds and communication volume, there is a \emph{ third} parameter of interest, namely the \emph{ error probability} $p_{ \mathrm{ err}}$. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send $\Omega(k + \log p_{ \mathrm{ err}}^{ -1})$ bits. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k + \log p_{ \mathrm{ err}}^{ -1})$ communication and $O(\log^* k)$ rounds? In this paper we prove that there is no universally optimal algorithm, and complement the existing round-communication tradeoffs with a new tradeoff between rounds, communication, and probability of error. In particular: 1. Any protocol for solving Multiple Equality Testing in $r$ rounds with failure probability $2^{ -E}$ has communication volume $\Omega(Ek^{ 1/r})$. 2. There exists a protocol for solving Multiple Equality Testing in $r + \log^*(k/E)$ rounds with $O(k + rEk^{ 1/r})$ communication, thereby essentially matching our lower bound and that of Sa\u{ g}lam and Tardos. Our original motivation for considering $p_{ \mathrm{ err}}$ as an independent parameter came from the problem of enumerating triangles in distributed ($\textsf{ 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/\operatorname{ poly}(n)$.
Categories: cs.IT cs.CC math.IT