Theory Seminar: Partition Arguments in Multiparty Communication Complexity

Enav Weinreb (Computer Science, Technion)

Sunday, 30.11.2008, 12:00

Taub 601

Consider the ``plain'' multiparty communication complexity model,
where k players $P_1,\dots,P_k$ holding inputs
$x_1,\dots,x_k\in\bit^n$ (respectively) communicate in order to
compute the value $f(x_1,\dots,x_k)$. The main lower bound
technique for such communication problems is that of {\em
partition arguments}: partition the $k$-players into two disjoint
sets of players and find a lower bound for the induced two-party
communication complexity problem. In this paper, we study the
power of the partition arguments method. Our two main results are
very different in nature:

For {\em randomized} communication complexity we show that partition arguments may be exponentially far from the true communication complexity. That is, we prove that there exists a $3$-argument function $f$ whose communication complexity is $\Omega(n)$ but partition arguments can only yield an $\Omega(\log n)$ lower bound. The same holds for nondeterministic communication complexity.

For the case of {\em deterministic} communication complexity, we prove that finding significant gaps, between the true communication complexity and the best lower bound that can be obtained via partition arguments, implies progress on (a generalized version of) the ``log rank conjecture'' of communication complexity. This explains why partition arguments seem to yield good lower bounds in this case.

Joint work with Eyal Kushilevitz

For {\em randomized} communication complexity we show that partition arguments may be exponentially far from the true communication complexity. That is, we prove that there exists a $3$-argument function $f$ whose communication complexity is $\Omega(n)$ but partition arguments can only yield an $\Omega(\log n)$ lower bound. The same holds for nondeterministic communication complexity.

For the case of {\em deterministic} communication complexity, we prove that finding significant gaps, between the true communication complexity and the best lower bound that can be obtained via partition arguments, implies progress on (a generalized version of) the ``log rank conjecture'' of communication complexity. This explains why partition arguments seem to yield good lower bounds in this case.

Joint work with Eyal Kushilevitz