Volume 2020

The communication complexity of the inevitable intersection problem

Dmitry Gavinsky
Institute of Mathematics
Prague, Czech Republic
gavinsky AT math DOT cas DOT cz

August 24, 2020

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)