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.