Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-064 | 24th April 2014 09:43

The Power of Super-logarithmic Number of Players


Authors: Arkadev Chattopadhyay, Michael Saks
Publication: 25th April 2014 12:00
Downloads: 899


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 size. These are functions of the form $f \circ g$ where $f$ is a symmetric $b$-variate function, and $g$ is a $k r$-variate function and $f \circ g(A)$ is defined, for a $k \times br$ matrix to be $f(g(A^1),\ldots,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^r$. Ada (ICALP'12) previously obtained \emph{simultaneous} and deterministic efficient protocols for composed functions of block-width $r=1$. The new protocol is the first to work for block composed functions with $r>1$. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

ISSN 1433-8092 | Imprint