7
$\begingroup$

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?

Improve this question
$\endgroup$
  • 11
    $\begingroup$ It's known as "number in hand". $\endgroup$ – Yuval Filmus Nov 21 '13 at 4:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeremy Kun Nov 22 '13 at 5:30
  • $\begingroup$ Rather, you should answer your own question with a summary of the result you mention, and accept it (you will be able to, eventually). $\endgroup$ – Yuval Filmus Nov 22 '13 at 8:35
4
$\begingroup$

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

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Conference version: 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. $\endgroup$ – András Salamon Mar 10 '14 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.