Enav Weinreb, CWI Amsterdam
Consider the "plain" multiparty communication complexity model, where k players P_{1} , ... , P_{k} holding inputs x_{1} , ... , 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 such communication 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 in different communication complexity models: the deterministic, the non-deterministic and the randomized models of communication. |