Abstract.
The two-party communication complexity of Boolean function f is known to be at least log rank (M f ), i.e., the logarithm of the rank of the communication matrix of f [19]. Lovász and Saks [17] asked whether the communication complexity of f can be bounded from above by (log rank (M f ))c , for some constant c . The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f , it remained a difficult open problem.
We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L 1 norm of function f , for arbitrary Boolean function f .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 24, 1996; revised October 15, 1997.
Rights and permissions
About this article
Cite this article
Grolmusz, V. Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions . Algorithmica 23, 341–353 (1999). https://doi.org/10.1007/PL00009265
Issue Date:
DOI: https://doi.org/10.1007/PL00009265