On information complexity in the broadcast model

DOI10.1145/2767386.2767425MaRDI QIDQ2796271zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Rotem Oshman

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2767386.2767425

zbMATH Keywords

communication complexitycompressioninformation complexityset disjointness

Mathematics Subject Classification ID

Distributed systems (68M14) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• Interactive information complexity
• Interactive Information Complexity
• Interactive information complexity
• From information to exact communication
• Interactive compression for multi-party protocol

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(14)

• Information-theoretic broadcast with dishonest majority for long messages
• Information complexity and applications.
• Multi-party threshold private set intersection with sublinear communication
• The effect of range and bandwidth on the round complexity in the congested clique model
• A trade-off between information and communication in broadcast protocols
• scientific article; zbMATH DE number 1156839 (Why is no real title available?)
• Interactive information complexity
• Information complexity is computable
• Exponential separation of communication and external information
• Exponential separation of communication and external information
• Interactive information complexity
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• The communication complexity of distributed maximization
• Multi-party set disjointness and intersection with bounded dependence

This page was built for publication: On information complexity in the broadcast model

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