On multi-partition communication complexity
We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k + 1 partitions instead of k may decrease the communication complexity from Theta(n) to Theta(log k). 2. Certain linear codes are hard for k-partition protocols even when k may be exponentially large (in the input size). On the other hand, one can show that all characteristic functions of linear codes are easy for randomized OBDDs. 3. It is proved that there are subfunctions of the triangle-freeness function and the function circle plus CLIQUE(3,n) that are hard for multi-partition protocols. As an application, strongly exponential lower bounds on the size of nondeterministic read-once branching programs for these functions are obtained, solving an open problem of Razborov [Proceedings of the eighth FCT, LNCS 529, Springer, 1991, pp. 47-60]. (C) 2004 Elsevier Inc. All rights reserved.
multi-partition communication complexity non-obliviousness lower bounds read-once branching programs computational complexity complexity hierarchy