License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.596
URN: urn:nbn:de:0030-drops-47243
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4724/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Arkadev ; Saks, Michael E.

The Power of Super-logarithmic Number of Players

pdf-format:
41.pdf (0.4 MB)

Abstract

In the `Number-on-Forehead' (NOF) model of multiparty communication,
the input is a k times m boolean matrix A (where k is the number of players) and Player i sees all bits except those in the i-th row, and the players communicate by broadcast in order to evaluate a specified function f at A.

We discover new computational power when k exceeds log m. We give a protocol with communication cost poly-logarithmic in m, for block composed functions with limited block width. These are functions
of the form f o g where f is a symmetric b-variate function, and g is a (kr)-variate function and (f o g)(A) is defined, for a k times (br) matrix to be f(g(A-1),...,g(A-b)) where A-i is the i-th (k times r) block of A. Our protocol works provided that k > 1+ ln b + (2 to the power of r).

Ada et al. (ICALP'2012) previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width one. The new protocol is the first to work for block composed functions with block-width greather than one. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2014:4724,
  author =	{Arkadev Chattopadhyay and Michael E. Saks},
  title =	{{The Power of Super-logarithmic Number of Players}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{596--603},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4724},
  URN =		{urn:nbn:de:0030-drops-47243},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.596},
  annote =	{Keywords: Communication complexity, Number-On-Forehead model, composed functions}
}

Keywords: Communication complexity, Number-On-Forehead model, composed functions
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI