The communication complexity of the inevitable intersection problem

0532192 - MÚ 2021 RIV US eng J - Journal Article
Gavinsky, Dmitry
The communication complexity of the inevitable intersection problem.
Chicago Journal of Theoretical Computer Science. Roč. 2020, April (2020), č. článku 3. ISSN 1073-0486
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : communication complexity
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Method of publishing: Open access
https://doi.org/10.4086/cjtcs.2020.003

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 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 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 (II).
Permanent Link: http://hdl.handle.net/11104/0310771