Coding for Interactive Communication
summary
Describes concrete interactive coding results: any T-step interactive protocol can be simulated with only a constant-rate overhead using either randomized hashing and backtracking or algebraic constructions, achieving error probability like exp(−T/polylog T) with shared randomness and tolerating adversarial flips up to about 1/4 noise threshold. Key tools are tree codes (existential, not efficiently constructible in full generality) and a practical hash-and-backtrack method; multi‑party simulations incur an extra ~log n slowdown and recent work tightens capacity to 1 − Θ(√H(ε)).
AI-written summary · about
chapters (10)
- 0:00Start
- 0:20Absolute Basics
- 0:49Coding Theory
- 6:34Convolutional Codes
- 7:47Basic Model for Communication Complexity
- 9:55The Calvin and the Librarian Problem
- 14:53Error Correction
- 24:52What Happens in Interactive Communication
- 34:10Tree Codes
- 41:32Problem Statement
related talks
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
32mApproximate coding computing
31mMulti-version Coding and Shared Memory Emulation
31mAlgebraic Coding Problems From Quantum Fault-Tolerance
01h 03mClosing Keynote Day 2
58mThe Communication Complexity Landscape of Information-theoretic MPC
51mConvertible codes: Adaptive coding for large-scale data storage