The Communication Complexity of Set Intersection and Multiple Equality Testing
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\u{g}lam and Tardos and Brody et al. showed that for these types of problems, one can achieve optimal communication volume of …