Information Equals Amortized Communication
From MaRDI portal
Publication:5495039
DOI10.1109/FOCS.2011.86zbMath1292.94008arXiv1106.3595OpenAlexW2086467753MaRDI QIDQ5495039
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1106.3595
Information theory (general) (94A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Network protocols (68M12)
Related Items (21)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ On Slepian-Wolf theorem with interaction ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ Direct sum fails for zero-error average communication ⋮ Certifying equality with limited interaction ⋮ A discrepancy lower bound for information complexity ⋮ Unnamed Item ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Communication and information complexity ⋮ Deterministic compression with uncertain priors ⋮ Information value of two-prover games ⋮ Information complexity and applications. ⋮ Information lower bounds via self-reducibility ⋮ On Slepian–Wolf Theorem with Interaction ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ New Strong Direct Product Results in Communication Complexity
This page was built for publication: Information Equals Amortized Communication
