A communication-randomness tradeoff for two-processor systems

DOI10.1006/INCO.1995.1011MaRDI QIDQ1891144zbMATH OpenOpenAlexFDO

Authors Rudolf Fleischer, Hermann Jung, K. Mehlhorn

Publication date 28 May 1995

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1995.1011

zbMATH Keywords

communication complexityLas Vegas protocol

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Communication theory (94A05)

Recommendations

• LATIN 2004: Theoretical Informatics
• Average and randomized communication complexity
• scientific article; zbMATH DE number 1769898
• The randomized communication complexity of set disjointness
• Three results on interactive communication

Cited in

(8)

• On multi-partition communication complexity
• scientific article; zbMATH DE number 4055049 (Why is no real title available?)
• The Power of Shared Randomness in Uncertain Communication
• scientific article; zbMATH DE number 7204504 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Bounds on tradeoffs between randomness and communication complexity
• Communication complexity of equality and error-correcting codes
• Randomized function evaluation on a ring

This page was built for publication: A communication-randomness tradeoff for two-processor systems

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