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 Θ (n) to Θ (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 ⊕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 eighth FCT NCS 529, Springer, 1991, pp. 47–60].

Authors

• Pavol Ďuriš
• Juraj Hromkovič
• Stasys Jukna
• Martin Sauerhoff
• Georg Schnitger

Keywords

• Computational complexity
• Multi-partition communication complexity
• Non-obliviousness
• Lower bounds
• Complexity hierarchy
• Read-once branching programs