The Communication Complexity of Set Intersection and Multiple Equality Testing

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ğlam and Tardos [ST13] and Brody et al. [BCK + 16] 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 [ST13, BCK + 16] that this is one point along the optimal round-communication tradeoff 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 Set Intersection or Equality Testing need to send at least Ω(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 complement the existing round-communication tradeoffs [ST13, BCK + 16] with a new tradeoff between rounds, communication, and probability of error. In particular:

• Any protocol for solving Multiple Equality Testing in r rounds with failure probability p err = 2 -E has communication volume Ω(Ek 1/r ).

• We present several algorithms for Multiple Equality Testing (and its variants) that match or nearly match our lower bound and the lower bound of [ST13, BCK + 16].

• Lower bounds on Equality Testing extend to Set Intersection, for every r, k, and p err (which is trivial); in the reverse direction, we prove upper bounds on Equality Testing for r, k, p err imply similar upper bounds on Set Intersection 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 ∆. We prove that this problem can be solved in O(∆/log n+log log ∆) time with high probability 1 -1/poly(n). This beats the trivial (deterministic) O(∆)-time algorithm and is superior to the Õ(n 1/3 ) algorithm of [CPZ19, CS19] when ∆ = Õ(n 1/3 ).