Tutorial on Coding for Interactive Communication: Introduction and Overview
summary
Tutorial explains a concrete simulation: reduce arbitrary interactive protocols to the pointer-jumping hard case, protect each step with a tree code and prove correctness by tracking announced-prefix times TK and decoded-prefix consistency MR. The coded protocol tolerates about 1/4 error rate with a constant alphabet (binary version incurs an extra constant), and yields two constructions that work: a depth-resilient circuit against ~10% AND/OR flips and an O(log n)-dimensional L1 embedding for trees; an explicit treecode via complex roots is conjectured.
AI-written summary · about
chapters (13)
- 0:00Intro
- 8:16Outline
- 16:15The trivial protocol
- 19:49Tree code
- 26:36Tree Codes
- 29:00Using Tree Codes
- 30:37Tree Code Example
- 34:24Protocol Explanation
- 41:31Notation
- 46:32Mr
- 51:46Lemma
- 55:25Proof
- 58:24Reducing the alphabet size
related talks
01h 04mInformation Theory in Computational Complexity I
01h 22mTutorial 5: The GCT Chasm II
53mA Commentary on the Collision of Worlds
59mKEYNOTE: The Shape of a Program
01h 01mThe Gospel According to TCS
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
54mPanel Discussion
31mOrthogonal Remarks