scientific article; zbMATH DE number 6696541

DOI10.4230/LIPICS.APPROX-RANDOM.2014.721zbMATH Open1359.68070MaRDI QIDQ2969658FDOQ2969658

Authors:

Publication date: 22 March 2017

Title of this publication is not available (Why is that?)

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

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)

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)