Chicago Journal of Theoretical Computer Science

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


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:

DOI: 10.4086/cjtcs.2020.003

[] Volume 2020, Article 2
[back] Volume 2020 [back] Published articles
[CJCTS home]