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

Faculty of Engineering and Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

18 Scopus citations

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.

Original language	English
Title of host publication	Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings
Publisher	Springer Verlag
Pages	83-95
Number of pages	13
ISBN (Print)	9783319096193
DOIs	https://doi.org/10.1007/978-3-319-09620-9_8
State	Published - 2014
Event	21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014 - Takayama, Japan Duration: 23 Jul 2014 → 25 Jul 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8576 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014
Country/Territory	Japan
City	Takayama
Period	23/07/14 → 25/07/14

Access to Document

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

Cite this

Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2014). The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. In 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. in 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, Japan, 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).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this