The Communication Complexity of Set Intersection and Multiple Equality Testing
share
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. Brody et al. and Sağlam and Tardos 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 third parameter of interest, namely the error probabilityp_err. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send Ω(k + log p_err^-1) bits. Is it possible to simultaneously achieve optimality in all three parameters, namely O(k + log p_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 Ω(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ğlam and Tardos. 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 Δ. We prove that this problem can be solved in O(Δ/log n + loglogΔ) time with high probability 1-1/poly(n).
READ FULL TEXT