The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection

In this paper, we analyze the following communication complexity problem. It is a variant of the set-disjointness problem, denoted PDISJ_{log N}, 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² 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² 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² N) lower bound for PDISJ_{log N} 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.