ECCC-Report TR09-010https://eccc.weizmann.ac.il/report/2009/010Comments and Revisions published for TR09-010en-usThu, 05 Feb 2009 19:58:40 +0200
Paper TR09-010
| Lower bounds on the randomized communication complexity of read-once functions |
Nikos Leonardos,
Michael Saks
https://eccc.weizmann.ac.il/report/2009/010We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.
A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it.
The complexity of the evaluation of general read-once formulae, has attracted interest mainly in the decision tree model. In the communication complexity model, many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form $n(f)/c^d(f)$, where $n(f)$ is the number of variables and $d(f)$ the depth of the formula, and they are optimal up to the constant $c$ in the denominator.
Thu, 05 Feb 2009 19:58:40 +0200https://eccc.weizmann.ac.il/report/2009/010