Interactive information complexity

DOI10.1145/2213977.2214025zbMath1286.94047OpenAlexW2123346469MaRDI QIDQ5415498

Mark Braverman

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214025

zbMATH Keywords

information theoryprivacyinformation complexitycommunication complexityinteractive computation

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Source coding (94A29)

Related Items (13)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Certifying equality with limited interaction ⋮ A discrepancy lower bound for information complexity ⋮ Making Randomness Public in Unbounded-Round Information Complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ The Hardness of Being Private ⋮ Unnamed Item ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Quantum conditional mutual information and approximate Markov chains ⋮ Information lower bounds via self-reducibility ⋮ The Communication Complexity of Distributed epsilon-Approximations

This page was built for publication: Interactive information complexity