How to compress interactive communication

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

zbMATH Keywords

compressioninformation theorycommunication complexitydirect sum

Mathematics Subject Classification ID

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 (23)

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 ⋮ Communication lower bounds of key-agreement protocols via density increment arguments ⋮ 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