Communication complexity of set-disjointness for all probabilities

DOI10.4086/TOC.2016.V012A009MaRDI QIDQ2816409zbMATH OpenOpenAlexFDO

Authors Mika Göös, Thomas Watson

Publication date 22 August 2016

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2016.v012a009

zbMATH Keywords

communication complexitycomplexity classesset-disjointness

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 6696541
• The randomized communication complexity of set disjointness
• The Probabilistic Communication Complexity of Set Intersection
• The multiparty communication complexity of set disjointness
• The multiparty communication complexity of set disjointness
• The communication complexity of multiparty set disjointness under product distributions
• Deterministic communication complexity of set intersection
• Communication complexity theory: thirty-five years of set disjointness
• Beyond set disjointness: the communication complexity of finding the intersection
• Probabilistic communication complexity

Cites work

• scientific article; zbMATH DE number 6292622 (Why is no real title available?)
• Lower Bounds for Swapping Arthur and Merlin
• The pattern matrix method

Cited in

(12)

• The landscape of communication complexity classes
• On the streaming indistinguishability of a random permutation and a random function
• Communication complexity with small advantage
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• The randomized communication complexity of set disjointness
• The Probabilistic Communication Complexity of Set Intersection
• A lower bound for sampling disjoint sets
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• scientific article; zbMATH DE number 7250149 (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?)
• A hierarchy of constant communication complexity

This page was built for publication: Communication complexity of set-disjointness for all probabilities

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