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

Florent Becker; Pedro Montealegre; Ivan Rapaport; Ioan Todinca

doi:10.1007/978-3-319-09620-9_8

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

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Facultad de Ingeniería y Ciencias

Producción científica: Capítulo del libro/informe/acta de congreso › Contribución a la conferencia › revisión exhaustiva

16 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 original	Inglés
Título de la publicación alojada	Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings
Editorial	Springer Verlag
Páginas	83-95
Número de páginas	13
ISBN (versión impresa)	9783319096193
DOI	https://doi.org/10.1007/978-3-319-09620-9_8
Estado	Publicada - 2014
Evento	21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014 - Takayama, Japón Duración: 23 jul. 2014 → 25 jul. 2014

Serie de la publicación

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

Conferencia

Conferencia	21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014
País/Territorio	Japón
Ciudad	Takayama
Período	23/07/14 → 25/07/14

Acceder al documento

10.1007/978-3-319-09620-9_8

Citar esto

Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2014). The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. En Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings (pp. 83-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8576 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-09620-9_8

Becker, Florent ; Montealegre, Pedro ; Rapaport, Ivan et al. / The simultaneous number-in-hand communication model for networks : Private coins, public coins and determinism. Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings. Springer Verlag, 2014. pp. 83-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{263853c66bff4c168d9dae668371e720,

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

abstract = "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.",

author = "Florent Becker and Pedro Montealegre and Ivan Rapaport and Ioan Todinca",

note = "Funding Information: This work has been partially supported by CONICYT via Basal in Applied Mathematics (I.R.), N{\'u}cleo Milenio Informaci{\'o}n y Coordinaci{\'o}n en Redes ICM/FI P10-024F (I.R.) and Fondecyt 1130061 (I.R.); 21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014 ; Conference date: 23-07-2014 Through 25-07-2014",

year = "2014",

doi = "10.1007/978-3-319-09620-9_8",

language = "English",

isbn = "9783319096193",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "83--95",

booktitle = "Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings",

}

Becker, F, Montealegre, P, Rapaport, I & Todinca, I 2014, The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. En Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8576 LNCS, Springer Verlag, pp. 83-95, 21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014, Takayama, Japón, 23/07/14. https://doi.org/10.1007/978-3-319-09620-9_8

The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. / Becker, Florent; Montealegre, Pedro; Rapaport, Ivan et al.
Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings. Springer Verlag, 2014. p. 83-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8576 LNCS).

Producción científica: Capítulo del libro/informe/acta de congreso › Contribución a la conferencia › revisión exhaustiva

TY - GEN

T1 - The simultaneous number-in-hand communication model for networks

T2 - 21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014

AU - Becker, Florent

AU - Montealegre, Pedro

AU - Rapaport, Ivan

AU - Todinca, Ioan

N1 - Funding Information: This work has been partially supported by CONICYT via Basal in Applied Mathematics (I.R.), Núcleo Milenio Información y Coordinación en Redes ICM/FI P10-024F (I.R.) and Fondecyt 1130061 (I.R.)

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958545674&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-09620-9_8

DO - 10.1007/978-3-319-09620-9_8

M3 - Conference contribution

AN - SCOPUS:84958545674

SN - 9783319096193

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 83

EP - 95

BT - Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings

PB - Springer Verlag

Y2 - 23 July 2014 through 25 July 2014

ER -

Becker F, Montealegre P, Rapaport I, Todinca I. The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. En Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings. Springer Verlag. 2014. p. 83-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-09620-9_8

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

Resumen

Serie de la publicación

Conferencia

Acceder al documento

Huella

Citar esto