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 complexityhierarchy resultsprobabilistic complexity classesseparation results

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)

Review text

The communication complexity of a Boolean function f equals the number of bits which have to be exchanged between two processors each knowing some part of the input x in order to compute f(x). This nonuniform complexity measure has found a lot of applications in complexity theory, e.g. in distributed computing, lower bounds for the VLSI complexity or monotone circuits. This paper is a major step in building a complexity theory on this complexity measure. Hence, a large number of results are proved. For most of the closure properties it is decided whether they are fulfilled. Perhaps even more important are hierarchy results, i.e. the result that a Boolean hierarchy does not collapse. Within these hierarchies also probabilistic complexity classes like the class C-BPP, the communication complexity counterpart of BPP, are investigated.

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

(13)

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

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)