Three results on interactive communication

DOI10.1109/18.259644MaRDI QIDQ4307373zbMATH OpenOpenAlexFDO

Authors Moni Naor, Alon Orlitsky, Peter W. Shor

Publication date 3 October 1994

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/4998afce9a9173fe777c9a1935fff4442d388dcb

zbMATH Keywords

amortized complexitybalanced pairscommunication complexitydata compressiondiscrepancyrandom pair

Mathematics Subject Classification ID

Communication theory (94A05) Source coding (94A29)

Recommendations

• Three messages are not optimal in worst case interactive communication
• Interactive Communication of Balanced Distributions and of Correlated Files
• scientific article; zbMATH DE number 826048

Cited in

(19)

• A general 4-words inequality with consequences for 2-way communication complexity
• Tight bounds for synchronous communication of information using bits and silence
• Protocols for asymmetric communication channels
• On Slepian-Wolf theorem with interaction
• A communication-randomness tradeoff for two-processor systems
• Communication with imperfectly shared randomness
• scientific article; zbMATH DE number 4191079 (Why is no real title available?)
• Worst Case Nonzero-Error Interactive Communication
• Interactive Communication of Balanced Distributions and of Correlated Files
• Three messages are not optimal in worst case interactive communication
• On interactive communication
• Coding for computing
• Amortized Communication Complexity
• scientific article; zbMATH DE number 826048 (Why is no real title available?)
• Repeated communication and Ramsey graphs
• Amortized communication complexity of an equality predicate
• On Slepian-Wolf theorem with interaction
• Communication and information complexity
• Ning Cai's work on communication complexity

This page was built for publication: Three results on interactive communication

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