Title: The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
Abstract: In this paper, we analyze the following communication complexity problem. It is a variant of the set-disjointness problem, denoted PDISJ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">log N</sub> , where each of Alice and Bob gets as an input a subset of [N] of size at most log N, with the promise that the intersection of the two subsets is of size at most 1. We provide an almost tight lower bound of ¿¿(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N) on the deterministic communication complexity of the problem. The main motivation for studying this problem comes from the so-called "clique vs. independent-set" problem, introduced by Yannakakis (1988). Proving an ¿(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N) lower bound on the communication complexity of the clique vs. independent-set problem for all graphs is a long standing open problem with various implications. Proving such a lower bound for random graphs is also open. In such a graph, both the cliques and the independent sets are of size O(log N) (and obviously their intersection is of size at most 1). Hence, our ¿¿(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N) lower bound for PDISJ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">log N</sub> can be viewed as a first step in this direction. Interestingly, we note that standard lower bound techniques cannot yield the desired lower bound. Hence, we develop a novel adversary argument that may find other applications.
Publication Year: 2009
Publication Date: 2009-10-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 10
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot