Sparse and Lopsided Set Disjointness via Information Theory
From MaRDI portal
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)
Recommendations
- scientific article; zbMATH DE number 1333601
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- scientific article; zbMATH DE number 3909739
- scientific article; zbMATH DE number 1072529
- The randomized communication complexity of set disjointness
- scientific article; zbMATH DE number 3984573
- On the sparse set conjecture for sets with low density
- On the distributional complexity of disjointness
- scientific article; zbMATH DE number 177818
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Cited in
(11)- Robust property-preserving hash functions for Hamming distance and more
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- The randomized communication complexity of set disjointness
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Certifying equality with limited interaction
- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
- scientific article; zbMATH DE number 7250148 (Why is no real title available?)
- The communication complexity of set intersection and multiple equality testing
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Approximate F₂-Sketching of Valuation Functions
- Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
This page was built for publication: Sparse and Lopsided Set Disjointness via Information Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167423)
