Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond

DOI10.1007/S00037-022-00225-6MaRDI QIDQ2159471zbMATH OpenOpenAlexFDO

Authors Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Publication date 1 August 2022

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.13712

zbMATH Keywords

communication complexitygeometric set systemsparsityVC dimension

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Communication theory (94A05)

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$. In this paper, 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 $widetildeThetaleft(dlogleft(n/dight)ight)$ 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 exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Thetaleft(dlogleft(n/dight)ight)$, and this is tight among all set systems of VC dimension $d$.

Recommendations

• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Separation dimension and sparsity
• Sparse and Lopsided Set Disjointness via Information Theory
• Sparsity and dimension
• Sparsity and dimension
• Sparse disjointed recovery from noninflating measurements
• Copositivity and sparsity relations using spectral properties
• Sparsity lower bounds for dimensionality reducing maps
• Structured sparsity: discrete and convex approaches

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• An information statistics approach to data stream and communication complexity
• Beyond set disjointness: the communication complexity of finding the intersection
• Communication Complexity
• Communication Complexity
• Communication complexity (for algorithm designers)
• Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n
• From information to exact communication
• Geometric discrepancy. An illustrated guide
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3271692 (Why is no real title available?)
• On data structures and asymmetric communication complexity
• On the density of families of sets
• On the distributional complexity of disjointness
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Private vs. common random bits in communication complexity
• Sparse and Lopsided Set Disjointness via Information Theory
• The Probabilistic Communication Complexity of Set Intersection
• The randomized communication complexity of set disjointness
• Two applications of information complexity

Cited in

(1)

• Tight lower bounds on the VC-dimension of geometric set systems

This page was built for publication: Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2159471)