<p>The "number in hand" model is the one I was thinking of, and there is quite a bit of literature about it. In particular I found this paper of Jeff Phillips, Elad Verbin, and Qin Zhang from SODA 2012 [1]. In particular they prove lower bounds on the problem I was interested in using, the undirected graph connectivity problem, of $\Omega(nk / \log^2(k))$. Here $k$ is the number of edges provided to each player and $n$ is the number of vertices in the graph.</p>

<p>[1] <a href="http://arxiv.org/abs/1107.2559" rel="nofollow">http://arxiv.org/abs/1107.2559</a></p>

CC BY-SA 3.0
2014-03-10T11:46:14.130Z
Conference version: http://dl.acm.org/citation.cfm?id=2095158 and note that for $k=2$ an $\Omega(n \log n)$ lower bound is known for undirected connectivity.  Also, in the paper $k$ is the number of parties, who partition the edges of the graph between themselves, not the number of edges provided to each party.
András Salamon
CC BY-SA 3.0
2013-11-22T14:34:43.030Z
2013-11-22T14:34:43.030Z
Jeremy Kun
<p>I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications.</p>

<p>A priori the definition of multiparty communication complexity is strange. Forgetting the fruitful applications of the "number on the forehead" model, I would imagine people first thought to have each player see only their <em>own</em> input and not <em>all but their own</em> inputs. The computation of the protocol would happen in parallel, and communication could be player-to-player or broadcast.</p>

<p>I have reason to believe that lower bounds in such a model will aid me in proving lower bounds in a problem I'm currently looking at. Does this model have a name? What is known about it?</p>

CC BY-SA 3.0
2013-11-21T04:06:58.193Z
It's known as "number in hand".
Yuval Filmus
CC BY-SA 3.0
2013-11-22T05:30:04.730Z
And that was enough to lead me to the SODA '12 Phillips-Verbin-Zhang paper which has a lower bound on graph connectivity for this model. Very much in the realm of what I was looking for. Put an answer and I'll accept it.
Jeremy Kun
CC BY-SA 3.0
2013-11-22T08:35:15.290Z
Rather, you should answer your own question with a summary of the result you mention, and accept it (you will be able to, eventually).
Yuval Filmus
<lower-bounds><communication-complexity>
Lower bounds on alternative models of multiparty communication complexity
Jeremy Kun
# Lower bounds on alternative models of multiparty communication complexity

(Asked by: username_0 on 2013-11-21)

I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications.

A priori the definition of multiparty communication complexity is strange. Forgetting the fruitful applications of the "number on the forehead" model, I would imagine people first thought to have each player see only their *own* input and not *all but their own* inputs. The computation of the protocol would happen in parallel, and communication could be player-to-player or broadcast.

I have reason to believe that lower bounds in such a model will aid me in proving lower bounds in a problem I'm currently looking at. Does this model have a name? What is known about it?

**Tags:** lower-bounds, communication-complexity

> **Comments:**
> **username_1**: It's known as "number in hand".  
> **username_0**: And that was enough to lead me to the SODA '12 Phillips-Verbin-Zhang paper which has a lower bound on graph connectivity for this model. Very much in the realm of what I was looking for. Put an answer and I'll accept it.  
> **username_1**: Rather, you should answer your own question with a summary of the result you mention, and accept it (you will be able to, eventually).  

---

## 1 answers

### Answer by username_0 on 2013-11-22. Score: 4 | Accepted answer

The "number in hand" model is the one I was thinking of, and there is quite a bit of literature about it. In particular I found this paper of Jeff Phillips, Elad Verbin, and Qin Zhang from SODA 2012 [1]. In particular they prove lower bounds on the problem I was interested in using, the undirected graph connectivity problem, of $\Omega(nk / \log^2(k))$. Here $k$ is the number of edges provided to each player and $n$ is the number of vertices in the graph.

[1] <http://arxiv.org/abs/1107.2559>

> **Comments:**
> **username_2**: Conference version: http://dl.acm.org/citation.cfm?id=2095158 and note that for $k=2$ an $\Omega(n \log n)$ lower bound is known for undirected connectivity.  Also, in the paper $k$ is the number of parties, who partition the edges of the graph between themselves, not the number of edges provided to each party.  

---

