Relations between communication complexity classes

DOI10.1016/0022-0000(90)90027-IzbMath0715.68029OpenAlexW2075106440MaRDI QIDQ751811

Bernd Halstenberg, K. Ruediger 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

probabilistic complexity classescommunication complexityseparation resultshierarchy 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)

Related Items (10)

On relations between counting communication complexity classes ⋮ Non-deterministic communication complexity with few witnesses ⋮ The landscape of communication complexity classes ⋮ Unbounded-error quantum query complexity ⋮ On Toda’s Theorem in Structural Communication Complexity ⋮ Lower bounds for the majority communication complexity of various graph accessibility problems ⋮ The communication complexity of enumeration, elimination, and selection ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Adventures in monotone complexity and TFNP ⋮ Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity

Cites Work

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

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