# Simultaneous Multiparty Communication Complexity of Composed Functions.

In the Number On the Forehead (NOF) multiparty communication model, $k$ players want to evaluate a function $F : X_1 \times\cdots\times X_k\rightarrow Y$ on some input $(x_1,\dots,x_k)$ by broadcasting bits according to a predetermined protocol. The input is distributed in such a way that each player $i$ sees all of it except $x_i$. In the simultaneous setting, the players cannot speak to each other but instead send information to a referee. The referee does not know the players' input, and cannot give any information back. At the end, the referee must be able to recover $F(x_1,\dots,x_k)$ from what she obtained.

A central open question, called the $\log n$ barrier, is to find a function which is hard to compute for $polylog(n)$ or more players (where the $x_i

So far, it was only known that $t=1$ is not enough for $MAJ\circ MAJ_t$ to break the $\log n$ barrier in the simultaneous deterministic NOF model. In this paper, we extend this result to any constant block-width $t>1$, by giving a protocol of cost $2^{O(2^t)}\log^{2^{t+1}}(n)$ for any symmetric composed function when there are $2^{\Omega(2^t)}\log n$ players.

Publisher URL: http://arxiv.org/abs/1710.01969

DOI: arXiv:1710.01969v2

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.