TY - GEN

T1 - Lower bounds on the randomized communication complexity of read-once functions

AU - Leonardos, Nikos

AU - Saks, Michael

PY - 2009

Y1 - 2009

N2 - We prove lower bounds on the randomized two-party communication complexity of functions that arise from readonce 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) is the depth of the formula, and they are optimal up to the constant c in the denominator.

AB - We prove lower bounds on the randomized two-party communication complexity of functions that arise from readonce 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) is the depth of the formula, and they are optimal up to the constant c in the denominator.

UR - http://www.scopus.com/inward/record.url?scp=70350675312&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350675312&partnerID=8YFLogxK

U2 - 10.1109/CCC.2009.32

DO - 10.1109/CCC.2009.32

M3 - Conference contribution

AN - SCOPUS:70350675312

SN - 9780769537177

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 341

EP - 350

BT - Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

T2 - 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

Y2 - 15 July 2009 through 18 July 2009

ER -