Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Communication Complexity: From Two-Party to Multiparty
verfasst von : Eyal Kushilevitz
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the multiparty communication complexity model, where
k
players holding inputs
x
1
,...,
x
k
communicate to compute the value
f
(
x
1
,...,
x
k
) of a function
f
known to all of them.
Yao’s classic two-party communication complexity model [3] is the special case
k
= 2 (see also [2]). In the first part of the talk, we survey some basic results regarding the two-party model, emphasizing methods for proving lower-bounds.
In the second part of the talk, we consider the case where there are at least three parties (
k
≥ 3). The main lower bound technique for the communication complexity of such multiparty problems is that of
partition arguments
: partition the
k
players into two disjoint sets of players and find a lower bound for the induced
two-party
communication complexity problem. We discuss the power of partition arguments for both deterministic and randomized protocols. (This part is based on a joint work with Jan Draisma and Enav Weinreb [1].)