Information Equals Amortized Communication

DOI10.1109/TIT.2014.2347282MaRDI QIDQ2986089zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Anup Rao

Publication date 16 May 2017

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

Full work available at URL https://doi.org/10.1109/tit.2014.2347282

Mathematics Subject Classification ID

Communication theory (94A05) Information theory (general) (94A15)

Cited in

(20)

• Information-theoretic approximations of the nonnegative rank
• Communication complexity with small advantage
• Simulation theorems via pseudo-random properties
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Relative discrepancy does not separate information and communication complexity
• Interactive Information Complexity
• Trading information complexity for error
• Simplified separation of information and communication
• Compressing interactive communication under product distributions
• Exponential separation of communication and external information
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Lifting Theorems for Equality
• Optimal separation and strong direct sum for randomized query complexity
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• Query-to-communication lifting using low-discrepancy gadgets
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of functions with large outputs
• The work of Mark Braverman
• A hierarchy of constant communication complexity
• Asymptotic spectra: theory, applications, and extensions

This page was built for publication: Information Equals Amortized Communication

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