Relations between communication complexity classes

DOI10.1016/0022-0000(90)90027-IMaRDI QIDQ751811zbMATH OpenOpenAlexFDO

Authors Bernd Halstenberg, Rüdiger Reischuk

Publication date 1990

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(90)90027-i

zbMATH Keywords

communication complexityseparation resultshierarchy resultsprobabilistic complexity classes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 3881884
• scientific article; zbMATH DE number 1011685
• scientific article; zbMATH DE number 4068270
• Probabilistic communication complexity
• Nondeterministic and randomized Boolean hierarchies in communication complexity

Cites work

• BPP and the polynomial hierarchy
• Probabilistic communication complexity
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(11)

• On Toda’s Theorem in Structural Communication Complexity
• Unbounded-error quantum query complexity
• The landscape of communication complexity classes
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• The communication complexity of enumeration, elimination, and selection
• Lower bounds for the majority communication complexity of various graph accessibility problems
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• scientific article; zbMATH DE number 3881884 (Why is no real title available?)
• On relations between counting communication complexity classes
• Non-deterministic communication complexity with few witnesses
• Adventures in monotone complexity and TFNP

This page was built for publication: Relations between communication complexity classes

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