The Library
Disjointness through the lens of Vapnik–Chervonenkis dimension : sparsity and beyond
Tools
Bhattacharya, Anup, Chakraborty, Sourav, Ghosh, Arijit, Mishra, Gopinath and Paraashar, Manaswi (2022) Disjointness through the lens of Vapnik–Chervonenkis dimension : sparsity and beyond. Computational Complexity, 31 (2). 9. doi:10.1007/s00037-022-00225-6 ISSN 1016-3328.
|
PDF
WRAP-Disjointness-lens-Vapnik–Chervonenkis-dimension-sparsity-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (498Kb) | Preview |
Official URL: https://doi.org/10.1007/s00037-022-00225-6
Abstract
The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $\Theta(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik–Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. The $d$-sparse set disjointness problem, where the sets have size at most $d$, is one such set system with VC dimension $d$. The deterministic and the randomized communication complexities of the $d$-sparse set disjointness problem have been well studied and are known to be $\Theta \left( d \log \left({n}/{d}\right)\right)$ and $\Theta(d)$, respectively, in the multi-round communication setting. In this paper, we address the question of whether the randomized communication complexity of the disjointness problem
is always upper bounded by a function of the VC dimension of the set system, and does there always exist a gap between the deterministic and randomized communication complexities of the disjointness problem
for set systems with small VC dimension.
We construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $\widetilde{\Theta}\left(d\log \left( n/d \right)\right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exist set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexities for the set intersection problem can be as high as $\Theta\left( d\log \left( n/d \right) \right)$.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Information theory, Mathematical optimization, Irregularities of distribution (Number theory) | ||||||
Journal or Publication Title: | Computational Complexity | ||||||
Publisher: | Springer | ||||||
ISSN: | 1016-3328 | ||||||
Official Date: | 5 July 2022 | ||||||
Dates: |
|
||||||
Volume: | 31 | ||||||
Number: | 2 | ||||||
Article Number: | 9 | ||||||
DOI: | 10.1007/s00037-022-00225-6 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Copyright Holders: | Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar | ||||||
Date of first compliant deposit: | 9 July 2022 | ||||||
Date of first compliant Open Access: | 11 July 2022 | ||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year