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

information theorycommunication complexityand/or treesread-once formulae

Mathematics Subject Classification ID

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

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)

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