2009 | OriginalPaper | Chapter
Partition Arguments in Multiparty Communication Complexity
Authors : Jan Draisma, Eyal Kushilevitz, Enav Weinreb
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Consider the “Number in Hand” multiparty communication complexity model, where
k
players
P
1
,...,
P
k
holding inputs
$x_1,\ldots,x_k\in{0, 1}^n$
(respectively) communicate in order to compute the value
f
(
x
1
,...,
x
k
). The main lower bound technique for the communication complexity of such problems is that of
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:
(i) For
randomized
communication complexity we show that partition arguments may be exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function
f
whose communication complexity is
Ω
(
n
) but partition arguments can only yield an
Ω
(log
n
) lower bound. The same holds for
nondeterministic
communication complexity.
(ii) For
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, would imply progress on (a generalized version of) the “log rank conjecture” of communication complexity.