Lower bounds on the randomized communication complexity of read-once functions (Q626679): Difference between revisions

A read-once formula is a Boolean formula using the logical connectives AND and OR with the property that every variable appears exactly once. A read-once threshold formula is more general in that it can also use threshold gates. The paper establishes lower bounds for the two-party communication complexity of functions computed by read-once formulae and by read-once threshold formulae. The lower bounds are of the form \(n/c^d\), where \(n\) is the number of variables, \(d\) is the depth of the formula, and \(c\) is a constant. The proofs use information-theoretical methods.