About: Multiparty communication complexity     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMultiparty_communication_complexity&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

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 , 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. The formal definition is as follows: players: intend to compute a Boolean function where the maximum is taken over all k-partitions of set .

AttributesValues
rdfs:label
  • Multiparty communication complexity (en)
rdfs:comment
  • 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 , 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. The formal definition is as follows: players: intend to compute a Boolean function where the maximum is taken over all k-partitions of set . (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • 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 , 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, 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: players: intend to compute a Boolean function On set of variables there is a fixed partition of classes , and player knows every variable, except those in , for . The players have unlimited computational power, and they communicate with the help of a blackboard, viewed by all players. The aim is to compute ), 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 and partition . The cost of a multiparty protocol is the maximum number of bits communicated for any from the set {0,1}n and the given partition . The -party communication complexity, of a function , with respect to partition , is the minimum of costs of those -party protocols which compute . The -party symmetric communication complexity of is defined as where the maximum is taken over all k-partitions of set . (en)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 46 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software