#

### Volume 2020

#### Article 3

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

#### The communication complexity of the inevitable intersection problem

Dmitry Gavinsky

Institute of Mathematics

Czech Academy of Sciences

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)
**BibTeX** entry for this
article (355 bytes)

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

Volume 2020, Article 2

Volume 2020
Published articles