Published by the Department of Computer Science, The University of Chicago.

Abstract

Set disjointness Disj is a central problem in communication complexity. Here Alice and Bob each receive a subset of an n-element universe, and they need to decide whether their inputs intersect or not. The communication complexity of this problem is relatively well understood, and in most models, including -- most famously -- interactive randomised communication with bounded error $\mathcal{R}$, the problem requires much communication.

In this work we were looking for a variation of Disj, as natural and simple as possible, for which the known lower bound methods would fail, and thus a new approach would be required in order to understand its $\mathcal{R}$-complexity. The problem that we have found is a relational one: each player receives a subset as input, and the goal is to find an element that belongs to both players. We call it inevitable intersection $\mathcal{II}$. The following list of its properties seem to let $\mathcal{II}$ resist the old lower bound techniques:

• the domain of $\mathcal{II}$ is $A\times B$, the product of the players' individual input spaces;
• $A\times B$ only contains intersecting pairs of subsets;
• the input comes from the uniform distribution over $A\times B$;
• $A\times B$ is chosen in a randomised fashion, both $A$ and $B$ being uniformly-random subsets of $2^{[n]}$ of size $2^{n^{\Theta(1)}}$.

In particular, complexity analysis of $\mathcal{II}$ cannot be based on the hardness of Disj (as no pair in $A\times B$ is disjoint); moreover, it cannot be based on any argument based on discrepancy (including corruption, smooth discrepancy and the like), as the problem allows for a cover of $A\times B$ by $n$ perfectly-monochromatic rectangles.

We are using an ad hoc technique to show that $\mathcal{II}$ is ultimately hard: it requires $\Omega(\log |A|)$ bits of interactive randomised communication. Besides its ability -- apparently unique -- to capture the complexity of the inevitable intersection, the new technique can also be applied to other ``search-like'' problems (including Disj), thus providing new insight into their communicational hardness.




• The article: PDF (343 KB)
• Source material: ZIP (77 KB)
• BibTeX entry for this article (355 bytes)

Submitted Submitted June 1, 2018, revised August 16, 2020, published August 24, 2020.

© 2020 Dmitry Gavinsky
Licensed under a Creative Commons Attribution License

Volume 2020, Article 2

Volume 2020

Published articles