Information Equals Amortized Communication

DOI10.1109/TIT.2014.2347282zbMath1360.94124OpenAlexW2066627246MaRDI QIDQ2986089

Anup Rao, Mark Braverman

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

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

Related Items (19)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Interactive Information Complexity ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Communication complexity with small advantage ⋮ The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ Information complexity of the AND function in the two-party and multi-party settings ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Exponential Separation of Communication and External Information ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

This page was built for publication: Information Equals Amortized Communication