How to Compress Asymmetric Communication
summary
Provides two concrete compression schemes and one explicit bound that helps when information is lopsided: converts any protocol into a bounded‑round “guess K bits” protocol using public randomness guessing, then applies Braverman–Rao to get communication about I_A + C^{3/4} I_B^{1/4} by setting K = C^{1/4} I_B^{-1/4} so rounds ≈ C^{3/4} I_B^{1/4}. Analysis uses Pinsker, Cauchy‑Schwarz and chain rule to bound expected mistakes and information; a small‑ε example shows the key lemma is tight.
AI-written summary · about
chapters (5)
- 0:00Start
- 5:31Asymmetric Communication
- 16:20Analysis
- 17:28Information Content
- 18:14Information learnt by Bob
related talks
58mThe Communication Complexity Landscape of Information-theoretic MPC
30mDistributed Statistical Estimation of Matrix Products with Applications
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
17mFrom Channel Assignment to Subgraph Isomorphism
57mCoding for Interactive Communication
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
33mGeometry of Secure Computation