From information to exact communication

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

zbMATH Keywords

information complexitycommunication complexitydisjointness

Mathematics Subject Classification ID

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