From information to exact communication
From MaRDI portal
Publication:5495785
DOI10.1145/2488608.2488628zbMath1293.68160OpenAlexW2078825942MaRDI QIDQ5495785
Denis Pankratov, Mark Braverman, Ankit Garg, Omri Weinstein
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488628
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication theory (94A05)
Related Items (19)
Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Common information and unique disjointness ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Direct sum fails for zero-error average communication ⋮ Certifying equality with limited interaction ⋮ Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Communication complexity with small advantage ⋮ Unnamed Item ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Information complexity and applications. ⋮ Information lower bounds via self-reducibility ⋮ Unnamed Item ⋮ Chang's lemma via Pinsker's inequality ⋮ Information complexity of the AND function in the two-party and multi-party settings ⋮ Unnamed Item ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity
This page was built for publication: From information to exact communication