Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond

DOI10.4230/lipics.approx/random.2020.23OpenAlexW3082477927MaRDI QIDQ6062144

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

Publication date: 31 October 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12626/pdf/LIPIcs-APPROX23.pdf/

zbMATH Keywords

VC dimensioncommunication complexitysparsityand geometric set system

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• 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
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Communication Complexity
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Geometric discrepancy. An illustrated guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond