scientific article; zbMATH DE number 6696541

DOI10.4230/LIPICS.APPROX-RANDOM.2014.721MaRDI QIDQ2969658zbMATH OpenFDO

Authors

Publication date 22 March 2017

zbMATH Keywords

communication complexityset-disjointnessall probabilities

Mathematics Subject Classification ID

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

Recommendations

• Communication complexity of set-disjointness for all probabilities
• 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
• Probabilistic communication complexity

Cited in

(6)

• A lower bound for sampling disjoint sets
• Communication costs in a geometric communication network
• Rectangles are nonnegative juntas
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• Communication complexity of set-disjointness for all probabilities
• The Probabilistic Communication Complexity of Set Intersection

This page was built for publication:

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