From information to exact communication

DOI10.1145/2488608.2488628MaRDI QIDQ5495785zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Ankit Garg, Denis Pankratov, O. Weinstein

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

communication complexitydisjointnessinformation complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Communication theory (94A05)

Recommendations

• scientific article; zbMATH DE number 7204267
• Trading information complexity for error
• Interactive information complexity
• Interactive Information Complexity
• Interactive information complexity

Cited in

(27)

• Information complexity and applications.
• Deterministic communication complexity of set intersection
• Trading information complexity for error. II: The case of a large error and the external information complexity
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Communication complexity with small advantage
• Chang's lemma via Pinsker's inequality
• On information complexity in the broadcast model
• 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
• Interactive Information Complexity
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Trading information complexity for error
• Interactive information complexity
• The communication complexity of the inevitable intersection problem
• Information lower bounds via self-reducibility
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• Interactive information complexity
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• The work of Mark Braverman
• Communication and information complexity
• A hierarchy of constant communication complexity
• Multi-party set disjointness and intersection with bounded dependence
• Communication memento: memoryless communication complexity
• Communication with endogenous information acquisition

This page was built for publication: From information to exact communication

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