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

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 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 languageEnglish
Title of host publicationStructural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Proceedings
PublisherSpringer Verlag
Pages83-95
Number of pages13
ISBN (Print)9783319096193
DOIs
StatePublished - 2014
Event21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014 - Takayama, Japan
Duration: 23 Jul 201425 Jul 2014

Publication series

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

Conference

Conference21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014
Country/TerritoryJapan
CityTakayama
Period23/07/1425/07/14

Fingerprint

Dive into the research topics of 'The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism'. Together they form a unique fingerprint.

Cite this