Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with non-obliviousness:
TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition 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 ... more >>>

ISSN 1433-8092 | Imprint