Tutorial on Efficient Coding for Interactive Communication via List Decoding
summary
Claims an adaptive interactive protocol tolerates up to 2/7 error rate (tight) while non‑adaptive protocols hit a 1/4 barrier, and achieves this by combining list decoding boost (run list decoders on log^2 n blocks, iterate ~1/epsilon times) with a tree‑intersection subroutine that finds the deepest consistent continuation. Construction uses hashing to name edges, error‑correcting codes to transmit candidate lists, and yields an efficient unique decoder assuming an efficient list decoder; the described block schedule (e.g. 300/300/100 example) concretely implements the scheme.
AI-written summary · about
chapters (8)
- 0:00Start
- 4:41Computational Efficiency
- 9:41Deterministic Polynomial Time Construction
- 16:57Adaptive Protocols
- 23:17Define Adaptive Protocols
- 1:07:42The List Decoder
- 1:08:10Error Correcting Code
- 1:11:39Error Correcting Codes
related talks
01h 04mInformation Theory in Computational Complexity I
01h 01mCoding for Modern Distributed Storage Systems I
59mDawn in the age of quantum fault tolerance
54mPanel Discussion
26mComplete Problems for Multi-Pseudodeterministic Computations
01h 10mDistribution Estimation and Applications I
23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
01h 09mInformation Theory in Computational Complexity IV