How to Compress Interactive Communication
From MaRDI portal
Publication:2848223
DOI10.1137/100811969zbMath1272.68138OpenAlexW2073639613MaRDI QIDQ2848223
Xi Chen, Mark Braverman, Anup Rao, Boaz Barak
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100811969
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 (28)
The Range of Topological Effects on Communication ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Direct sum fails for zero-error average communication ⋮ Certifying equality with limited interaction ⋮ Making Randomness Public in Unbounded-Round Information Complexity ⋮ The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Information complexity and applications. ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ Fooling Pairs in Randomized Communication Complexity ⋮ Unnamed Item ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Pointer chasing via triangular discrimination ⋮ Exponential Separation of Communication and External Information ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity
This page was built for publication: How to Compress Interactive Communication
