The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

18 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaStructural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings
EditorialSpringer Verlag
Páginas83-95
Número de páginas13
ISBN (versión impresa)9783319096193
DOI
EstadoPublicada - 2014
Evento21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014 - Takayama, Japón
Duración: 23 jul. 201425 jul. 2014

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen8576 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014
País/TerritorioJapón
CiudadTakayama
Período23/07/1425/07/14

Huella

Profundice en los temas de investigación de 'The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism'. En conjunto forman una huella única.

Citar esto