Sparse and Lopsided Set Disjointness via Information Theory

DOI10.1007/978-3-642-32512-0_44zbMath1372.68106OpenAlexW2176703953MaRDI QIDQ3167423

D. Sivakumar, Anirban Dasgupta, Ravi Kumar

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_44

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (10)

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Certifying equality with limited interaction ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Unnamed Item ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Unnamed Item ⋮ Robust property-preserving hash functions for Hamming distance and more ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing

This page was built for publication: Sparse and Lopsided Set Disjointness via Information Theory