How to compress interactive communication
From MaRDI portal
Publication:2875133
DOI10.1145/1806689.1806701zbMath1293.68116OpenAlexW1979790324MaRDI QIDQ2875133
Boaz Barak, Mark Braverman, Anup Rao, Xi Chen
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806701
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (22)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Interactive Information Complexity ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ A discrepancy lower bound for information complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ The Hardness of Being Private ⋮ Unnamed Item ⋮ The choice and agreement problems of a random function ⋮ Information lower bounds via self-reducibility ⋮ Lower Bounds for External Memory Integer Sorting via Network Coding ⋮ The direct sum of universal relations ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Geometric stability via information theory ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Unnamed Item
This page was built for publication: How to compress interactive communication
