“Multiparty communication complexity”的意思、由来-开放百科全书

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

In the traditional two–party communication game, introduced by {{harvtxt|Yao|1979}},^[1] two players, P₁ and P₂ attempt to compute a Boolean function

Player P₁ knows the value of x₂, P₂ knows the value of x₁, 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,^[2] is a powerful generalization of the 2–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₁,P₂,...,P_k intend to compute a Boolean function

On set S = {x₁,x₂,...,x_n} of variables there is a fixed partition A of k classes A₁,A₂,...,A_k, and player P₁ 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₁,x₂,...,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₁,x₂,...,x_n) and partition A = (A₁,A₂,...,A_k). The cost of a multiparty protocol is the maximum number of bits communicated for any x from the set {0,1}ⁿ 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

where the maximum is taken over all k-partitions of set x = (x₁,x₂,...,x_n).

Upper and lower bounds

For a general upper bound both for two and more players, let us suppose that A₁ is one of the smallest classes of the partition A₁,A₂,...,A_k. Then P₁ can compute any Boolean function of S with |A₁| + 1 bits of communication: P₂ writes down the |A₁| bits of A₁ on the blackboard, P₁ reads it, and computes and announces the value f(x). So, we can write:

Let y₁,y₂,...,y_k be n-bit vectors, and let Y be the n times k matrix, with k columns as the y₁,y₂,...,y_k vectors. Then GIP(y₁,y₂,...,y_k) is the number of the all-1 rows of matrix Y, taken modulo 2. In other words, if the vectors y₁,y₂,...,y_k correspond to the characteristic vectors of k subsets of an n element base-set, then GIP corresponds to the parity of the intersection of these k subsets.

For a general Boolean function f, one can bound the multiparty communication complexity of f by using its L₁ norm^[5] as follows:^[6]

Multiparty communication complexity and pseudorandom generators

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

1. ^{{citation | last = Yao | first = Andrew Chi-Chih | author-link = Andrew Yao | contribution = Some complexity questions related to distributive computing | doi = 10.1145/800135.804414 | pages = 209–213 | title = Proceedings of the 11th ACM Symposium on Theory of Computing (STOC '79) | year = 1979}}.
2. ^{{citation | last1 = Chandra | first1 = Ashok K. | author1-link = Ashok K. Chandra | last2 = Furst | first2 = Merrick L. | last3 = Lipton | first3 = Richard J. | author3-link = Richard J. Lipton | contribution = Multi-party protocols | doi = 10.1145/800061.808737 | pages = 94–99 | title = Proceedings of the 15th ACM Symposium on Theory of Computing (STOC '83) | year = 1983| isbn = 978-0897910996 }}.
3. ^¹²{{citation | last1 = Babai | first1 = László | author1-link = László Babai | last2 = Nisan | first2 = Noam | author2-link = Noam Nisan | last3 = Szegedy | first3 = Márió | author3-link = Mario Szegedy | doi = 10.1016/0022-0000(92)90047-M | issue = 2 | journal = Journal of Computer and System Sciences | mr = 1186884 | pages = 204–232 | title = Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs | volume = 45 | year = 1992}}.
4. ^{{citation | last = Grolmusz | first = Vince | doi = 10.1006/inco.1994.1051 | issue = 1 | journal = Information and Computation | mr = 1277711 | pages = 51–54 | title = The BNS lower bound for multi-party protocols is nearly optimal | volume = 112 | year = 1994}}.
5. ^{{citation | last1 = Bruck | first1 = Jehoshua | last2 = Smolensky | first2 = Roman | doi = 10.1137/0221003 | issue = 1 | journal = SIAM Journal on Computing | mr = 1148813 | pages = 33–42 | title = Polynomial threshold functions, AC⁰ functions, and spectral norms | volume = 21 | year = 1992| url = http://authors.library.caltech.edu/30356/1/BRUfocs90.pdf }}.
6. ^{{citation | last = Grolmusz | first = V. | doi = 10.1007/PL00009265 | issue = 4 | journal = Algorithmica | mr = 1673395 | pages = 341–353 | title = Harmonic analysis, real approximation, and the communication complexity of Boolean functions | volume = 23 | year = 1999| citeseerx = 10.1.1.53.6729 }}.