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

DOI10.1007/S00037-010-0292-2MaRDI QIDQ626679zbMATH OpenOpenAlexFDO

Authors Nikos Leonardos, Michael Saks

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-010-0292-2

zbMATH Keywords

and/or treescommunication complexityinformation theoryread-once formulae

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15)

Review text

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.

Recommendations

• Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
• How Do Read-Once Formulae Shrink?
• On directional vs. general randomized decision tree complexity for read-once formulas
• On read-once threshold formulae and their randomized decision tree complexity
• Bounding the randomized decision tree complexity of read-once Boolean functions

Cited in

(9)

• On read-once threshold formulae and their randomized decision tree complexity
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Communication complexity with small advantage
• Interactive Information Complexity
• Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
• Interactive information complexity
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Bounds on tradeoffs between randomness and communication complexity

This page was built for publication: Lower bounds on the randomized communication complexity of read-once functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626679)