Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-083 | 21st November 2003 00:00

One-Way Communication Complexity of Symmetric Boolean Functions


Authors: Jan Arpe, Andreas Jakoby, Maciej Liskiewicz
Publication: 1st December 2003 14:40
Downloads: 1931


We study deterministic one-way communication complexity
of functions with Hankel communication matrices.
Some structural properties of such matrices are established
and applied to the one-way two-party communication complexity
of symmetric Boolean functions.
It is shown that the number of required communication bits
does not depend on the communication direction, provided that
neither direction needs maximum complexity.
Moreover, in order to obtain an optimal protocol, it is
in any case sufficient to consider only the communication direction
from the party with the shorter input to the other party.
These facts do not hold for arbitrary Boolean functions in general.
Next, gaps between one-way and two-way communication
complexity for symmetric Boolean functions are discussed.
Finally, we give some generalizations to the case of multiple parties.

ISSN 1433-8092 | Imprint