ECCC-Report TR01-066https://eccc.weizmann.ac.il/report/2001/066Comments and Revisions published for TR01-066en-usSun, 30 Sep 2001 11:45:21 +0200
Paper TR01-066
| On Multipartition Communication Complexity |
Pavol Duris,
Juraj Hromkovic,
Stasys Jukna,
Martin Sauerhoff,
Georg Schnitger
https://eccc.weizmann.ac.il/report/2001/066We 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.
Sun, 30 Sep 2001 11:45:21 +0200https://eccc.weizmann.ac.il/report/2001/066