Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-083 | 21st November 2003 00:00

One-Way Communication Complexity of Symmetric Boolean Functions

RSS-Feed




TR03-083
Authors: Jan Arpe, Andreas Jakoby, Maciej Liskiewicz
Publication: 1st December 2003 14:40
Downloads: 4466
Keywords: 


Abstract:

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