Lesson plan
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. 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.…
Article summary
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.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.