Results on communication complexity classes

DOI10.1016/0022-0000(92)90025-EzbMath0762.68023OpenAlexW2174130830WikidataQ58063096 ScholiaQ58063096MaRDI QIDQ1190990

Walter L. Ruzzo, Tak-Wah Lam

Publication date: 27 September 1992

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(92)90025-e

zbMATH Keywords

hierarchiesseparation resultsalternating communication complexity hierarchiesCommunication complexityoptimal partition model

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Lower bounds for one-way probabilistic communication complexity and their application to space complexity ⋮ The landscape of communication complexity classes ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Lower bounds for one-way probabilistic communication complexity ⋮ Best-order streaming model ⋮ On the P versus NP intersected with co-NP question in communication complexity

Cites Work

• Probabilistic communication complexity
• Communication complexity
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Information Transfer under Different Sets of Protocols
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Optimal edge ranking of trees in linear time

This page was built for publication: Results on communication complexity classes