Number of the records: 1
The communication complexity of the inevitable intersection problem
- 1.
SYSNO ASEP 0532192 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Ostatní články Title The communication complexity of the inevitable intersection problem Author(s) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID Article number 3 Source Title Chicago Journal of Theoretical Computer Science. - : MIT Press - ISSN 1073-0486
Roč. 2020, April (2020)Number of pages 15 s. Language eng - English Country US - United States Keywords communication complexity Subject RIV IN - Informatics, Computer Science OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) R&D Projects GX19-27871X GA ČR - Czech Science Foundation (CSF) Method of publishing Open access Institutional support MU-W - RVO:67985840 DOI 10.4086/cjtcs.2020.003 Annotation 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). Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2021 Electronic address https://doi.org/10.4086/cjtcs.2020.003
Number of the records: 1