Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Multiparty_communication_complexity> ?p ?o. }
Showing items 1 to 13 of
13
with 100 items per page.
- Multiparty_communication_complexity abstract "In the two–party communication game, introduced by Yao (1979), two players, P1 and P2 attempt to compute a Boolean function Player P1 knows the value of x2, P2 knows the value of x1, but Pi does not know the value of xi, 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, it 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 roundtable, 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: P1,P2,...,Pk intend to compute a Boolean function On set S = {x1,x2,...,xn} of variables there is a fixed partition A of k classes A1,A2,...,Ak, and player P1 knows every variable, except those in Ai, 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(x1,x2,...,xn), 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 = (x1,x2,...,xn) and partition A = (A1,A2,...,Ak). 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 afunction 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 = (x1,x2,...,xn).".
- Multiparty_communication_complexity wikiPageID "34514105".
- Multiparty_communication_complexity wikiPageRevisionID "494671487".
- Multiparty_communication_complexity hasPhotoCollection Multiparty_communication_complexity.
- Multiparty_communication_complexity subject Category:Applied_mathematics.
- Multiparty_communication_complexity subject Category:Information_theory.
- Multiparty_communication_complexity comment "In the two–party communication game, introduced by Yao (1979), two players, P1 and P2 attempt to compute a Boolean function Player P1 knows the value of x2, P2 knows the value of x1, but Pi does not know the value of xi, for i = 1, 2. In other words, the players know the other's variables, but not their own.".
- Multiparty_communication_complexity label "Multiparty communication complexity".
- Multiparty_communication_complexity sameAs m.0j29rs6.
- Multiparty_communication_complexity sameAs Q6934835.
- Multiparty_communication_complexity sameAs Q6934835.
- Multiparty_communication_complexity wasDerivedFrom Multiparty_communication_complexity?oldid=494671487.
- Multiparty_communication_complexity isPrimaryTopicOf Multiparty_communication_complexity.