Relations between communication complexity classes
type: Item
instance of: scholarly article
title: Relations between communication complexity classes
zbMATH Open document ID: 0715.68029
DOI: 10.1016/0022-0000(90)90027-I
author: Bernd Halstenberg
author: Rüdiger Reischuk
published in: Journal of Computer and System Sciences
publication date: 1990-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 4178763
zbMATH Keywords: separation results
zbMATH Keywords: hierarchy results
zbMATH Keywords: communication complexity
zbMATH Keywords: probabilistic complexity classes
MaRDI profile type: Publication
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: BPP and the polynomial hierarchy
cites work: Probabilistic communication complexity
full work available at URL: 0022-0000(90)90027-i
OpenAlex ID: W2075106440
description: scientific article; zbMATH DE number 4178763