Tutorial on Capacity in Coding for Interactive Communication (Part 2 of 2)
summary
Provides an explicit coding scheme that attains overhead 1+Θ(√ε) by grouping communication into blocks of length block length b ≈ 1/√ε, hashing complete transcripts every block with fresh random seeds, exchanging hashes plus reported transcript lengths, and having only the deeper party backtrack by blocks on mismatch. Uses a potential argument to show each adversarial error costs O(b) work so total blowup is 1+Θ(√ε); for adversarial noise the proven bound is 1−Θ(√ε log log(1/ε)) and the scheme assumes a logarithmic-size alphabet.
AI-written summary · about
chapters (10)
- 0:00Introduction to the topic
- 1:19Setting the interactive scene
- 5:02Communication protocols
- 8:36The simple coding scheme idea
- 12:42Algorithm steps and hashing
- 17:26Refining the synchronization
- 21:34Correctness and potential
- 25:09Amortized complexity analysis
- 30:55Evaluating efficiency
- 34:31Limitations and conclusion
related talks
32mMust One Learn the Channel to Communicate at Capacity?
33mDeletion Codes in the High-noise and High-rate Regimes
32mDeterministic Rateless Codes for BSC
34mPolar Codes over q-ary Alphabets and Polynomially Fast Convergence to Shannon Capacity
01h 12mLightning Talks by Simons Institute Fellows
01h 14mPolar Codes III
20mBit Blasting Probabilistic Programs
17mAn Effectively Ω(c) Language and Runtime