A lower bound for sampling disjoint sets

DOI10.1145/3404858MaRDI QIDQ5053071zbMATH OpenOpenAlexFDO

Authors

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3404858

zbMATH Keywords

communication complexitysamplingset disjointness

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The randomized communication complexity of set disjointness
• Communication complexity of set-disjointness for all probabilities
• scientific article; zbMATH DE number 6696541
• The Quantum Communication Complexity of Sampling
• Randomness in Private Computations

Cited in

(3)

• Optimality of correlated sampling strategies
• Bottom-k and priority sampling, set similarity and subset sums with minimal independence
• Sampling, flowers and communication

This page was built for publication: A lower bound for sampling disjoint sets

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