TR01-066 Authors: Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

Publication: 30th September 2001 11:45

Downloads: 1942

Keywords:

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 a linear function in the

input size to a logarithmic function in 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 proven that there are subfunctions of the triangle-freeness function

and the function Parity-3-Clique which are hard for multipartition protocols.

As an application, truly exponential lower bounds

on the size of nondeterministic read-once branching programs

for these functions are obtained, solving an open problem of Razborov.