Multiparty communication complexity

In theoretical computer science, multiparty communication complexity is the study of communication complexity in the setting where there are more than two players.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

  • EnglishMultiparty communication complexity

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In theoretical computer science, multiparty communication complexity is the study of communication complexity in the setting where there are more than two players. In the traditional two-party communication game, introduced by , two players, P 1 and P 2 attempt to compute a Boolean function : f(x_1,x_2):\{0,1\}^n\to\{0,1\},\ x_1,x_2\in\{0,1\}^{n'},\ 2n'=n Player P 1 knows the value of x 2 , P 2 knows the value of x 1 , but P i does not know the value of x i , for i = 1, 2.

In other words, the players know the other's variables, but not their own. The minimum number of bits that must be communicated by the players to compute f is the communication complexity of f, denoted by κ(f). The multiparty communication game, defined in 1983, is a powerful generalization of the two-party case: Here the players know all the others' input, except their own.

Because of this property, sometimes this model is called "numbers on the forehead" model, since if the players were seated around a round table, each wearing their own input on the forehead, then every player would see all the others' input, except their own.…

In theoretical computer science, multiparty communication complexity is the study of communication complexity in the setting where there are more than two players. In the traditional two-party communication game, introduced by , two players, P 1 and P 2 attempt to compute a Boolean function f(x_1,x_2):\{0,1\}^n\to\{0,1\},\ x_1,x_2\in\{0,1\}^{n'},\ 2n'=n Player P 1 knows the value of x 2 , P 2 knows the value of x 1 , but P i does not know the value of x i , for i = 1, 2.

In other words, the players know the other's variables, but not their own. The minimum number of bits that must be communicated by the players to compute f is the communication complexity of f, denoted by κ(f). The multiparty communication game, defined in 1983, is a powerful generalization of the two-party case: Here the players know all the others' input, except their own.

Because of this property, sometimes this model is called "numbers on the forehead" model, since if the players were seated around a round table, each wearing their own input on the forehead, then every player would see all the others' input, except their own. The formal definition is as follows: k players: P_1, P_2,..., P_k intend to compute a Boolean function f(x_1,x_2,\ldots,x_n):\{0,1\}^n \to \{0,1\} On set S=\{x_1, x_2,..., x_n\} of variables there is a fixed partition A of k classes A_1,A_2,...,A_k , and player P_i knows every variable, except those in A_i , for i=1,2,...,k . The players have unlimited computational power, and they communicate with the help of a blackboard, viewed by all players.

The aim is to compute f(x_1,x_2,...,x_n ), such that at the end of the computation, every player knows this value. The cost of the computation is the number of bits written onto the blackboard for the given input x=(x_1,x_2,...,x_n) and partition A=(A_1,A_2,...,A_n) . The cost of a multiparty protocol is the maximum number of bits communicated for any x from the set {0,1} n and the given partition A . The k -party communication complexity, C^{(k)}_A (f) of a function f , with respect to partition A , is the minimum of costs of those k -party protocols which compute f . The k -party symmetric communication complexity of f is defined as C^{(k)}(f)=\max_AC^{(k)}_A(f) where the maximum is taken over all k-partitions of set x=(x_1,x_2,...,x_n) . C^{(k)}(f) = O\Bigg(k^2\log(n L_1(f))\Bigg\lceil{n L_1^2(f)\over2^k}\Bigg\rceil\Bigg)

Multiparty communication complexity and pseudorandom generators

A construction of a pseudorandom number generator was based on the BNS lower bound for the GIP function.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373750436 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001373750436 · captured 1788799839.0 · version history

Cite this page as: encyclopegia.org, “Multiparty communication complexity”, snapshot enwiki-001373750436. https://encyclopegia.org/a/multiparty-communication-complexity

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.