Lower bounds on the randomized communication complexity of read-once functions
DOI10.1007/S00037-010-0292-2zbMATH Open1229.68042OpenAlexW2097234068MaRDI QIDQ626679FDOQ626679
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
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
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (9)
- 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
- Title not available (Why is that?)
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
- On read-once threshold formulae and their randomized decision tree complexity
- Communication complexity with small advantage
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)
