Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 1 of 2)
summary
Shows a protocol that uses list decoding/list recovery to solve pointer‑jumping: given Alice and Bob’s layered edge sets the protocol outputs a small list of candidate leaves that provably contains the correct leaf, with list size Θ(1/ε) (order‑optimal). Uses tree‑code style encodings and alphabet reduction (polydepth → poly, then constant with more work) and achieves only constant communication overhead. Unique decoding breaks at the 1/4 noise threshold; with asymmetric noise unique decoding is possible when α+β < 1/4.
AI-written summary · about