The communication complexity of set intersection and multiple equality testing

DOI10.1137/1.9781611975994.105MaRDI QIDQ5146885zbMATH OpenOpenAlexFDO

Authors Dawei Huang, Seth Pettie, Yixiang Zhang, Zhijun Zhang

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11825

Mathematics Subject Classification ID

Combinatorial probability (60C05) Communication complexity, information complexity (68Q11) Randomized algorithms (68W20)

Abstract: 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$. Sau{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(lo{g}^{\ast }k)$ rounds. Aside from rounds and communication volume, there is a emph{third} parameter of interest, namely the emph{error probability} $p_{mathrmerr}$. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send $Omega(k+log{p}_{mathrmerr}^{-1})$ bits. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k+log{p}_{mathrmerr}^{-1})$ communication and $O(lo{g}^{\ast }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(E{k}^{1/r})$. 2. There exists a protocol for solving Multiple Equality Testing in $r+lo{g}^{\ast }(k/E)$ rounds with $O(k+rE{k}^{1/r})$ communication, thereby essentially matching our lower bound and that of Sau{g}lam and Tardos. Our original motivation for considering $p_{mathrmerr}$ as an independent parameter came from the problem of enumerating triangles in distributed ($extsfCONGEST$) networks having maximum degree $Delta$. We prove that this problem can be solved in $O(Delta/logn+loglogDelta)$ time with high probability $1-1/operatornamepoly(n)$.

Recommendations

• The communication complexity of set intersection and multiple equality testing
• Certifying equality with limited interaction
• Certifying equality with limited interaction
• Beyond set disjointness: the communication complexity of finding the intersection
• On the multiparty communication complexity of testing triangle-freeness

Cited in

(11)

• A new optimal distributed algorithm for the set intersection problem
• Still another rank determination of set intersection matrices with an application in communication complexity
• A note on improved results for one round distributed clique listing
• Beyond set disjointness: the communication complexity of finding the intersection
• Certifying equality with limited interaction
• Certifying equality with limited interaction
• The Probabilistic Communication Complexity of Set Intersection
• scientific article; zbMATH DE number 894723 (Why is no real title available?)
• On the multiparty communication complexity of testing triangle-freeness
• The communication complexity of set intersection and multiple equality testing
• Distributed subgraph finding: progress and challenges (invited talk)

This page was built for publication: The communication complexity of set intersection and multiple equality testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146885)