2014 | OriginalPaper | Buchkapitel
The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism
verfasst von : Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the multiparty communication model where players are the nodes of a network and each of these players knows his/her own identifier together with the identifiers of his/her neighbors. The players simultaneously send a unique message to a referee who must decide a graph property. The goal of this article is to separate, from the point of view of message size complexity, three different settings: deterministic protocols, randomized protocols with private coins and randomized protocols with public coins. For this purpose we introduce the boolean function
Twins
. This boolean function returns 1 if and only if there are two nodes with the same neighborhood.