Počet záznamů: 1
The communication complexity of the inevitable intersection problem
- 1.
SYSNO ASEP 0532192 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Ostatní články Název The communication complexity of the inevitable intersection problem Tvůrce(i) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID Číslo článku 3 Zdroj.dok. Chicago Journal of Theoretical Computer Science. - : MIT Press - ISSN 1073-0486
Roč. 2020, April (2020)Poč.str. 15 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova communication complexity Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GX19-27871X GA ČR - Grantová agentura ČR Způsob publikování Open access Institucionální podpora MU-W - RVO:67985840 DOI 10.4086/cjtcs.2020.003 Anotace 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). Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2021 Elektronická adresa https://doi.org/10.4086/cjtcs.2020.003
Počet záznamů: 1