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

DOI10.1007/S00037-022-00225-6zbMath1494.94001arXiv2006.13712OpenAlexW3037986963MaRDI QIDQ2159471

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

Publication date: 1 August 2022

Published in: Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

VC dimensioncommunication complexitysparsitygeometric set system

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Private vs. common random bits in communication complexity
• On the distributional complexity of disjointness
• On data structures and asymmetric communication complexity
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Beyond set disjointness
• Sparse and Lopsided Set Disjointness via Information Theory
• Communication Complexity (for Algorithm Designers)
• Two applications of information complexity
• 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
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Communication Complexity
• From information to exact communication
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Geometric discrepancy. An illustrated guide

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