Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
summary
Survey of multiparty interactive coding gives concrete conversions and limits: a randomized-BSC synchronous compiler yields a resilient protocol that uses O(t log d) rounds for a graph of max degree d, requiring per-link error p < poly(1/d) and giving rate about 1/log d (constant when d is constant); a different compiler for regular graphs with mixing time m achieves rate ~1/(m^3 log m) by routing encoded chunks over many short joint paths and relaying through √n-size subsets; adversarial schemes reach the maximal noise tolerance but with rate scaling like n/(m log n).
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:52Multiparty Interactive Communication
- 2:56Noisy Multiparty Interactive Communication
- 5:20Random Noise
- 10:14A Coding Scheme
- 12:48Example
- 17:09Analysis
- 20:44Probability
- 24:11Summary
- 25:21ABG
- 30:29Complete Graph
- 35:25Coding Scheme
- 40:07Discussion
related talks
57mCoding for Interactive Communication
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
58mThe Communication Complexity Landscape of Information-theoretic MPC
39mBroadcasting on Directed Acyclic Graphs
31mMulti-version Coding and Shared Memory Emulation
01h 03mClosing Keynote Day 2
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms