ECCC-Report TR14-064https://eccc.weizmann.ac.il/report/2014/064Comments and Revisions published for TR14-064en-usFri, 25 Apr 2014 12:00:41 +0300
Paper TR14-064
| The Power of Super-logarithmic Number of Players |
Arkadev Chattopadhyay,
Michael Saks
https://eccc.weizmann.ac.il/report/2014/064 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 et.al (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.Fri, 25 Apr 2014 12:00:41 +0300https://eccc.weizmann.ac.il/report/2014/064