Binary Codes with Resilience Beyond 1/4 via Interaction
summary
Constructs two-way binary codes that achieve resilience strictly >1/4 at constant rate with Bob sending one short reply, using a three-round non-adaptive protocol as a proof of concept. The scheme combines a length-16 list-decodable binary block (list size 3), a length-20 feedback block and a short 3-symbol confirmation, exploiting list-decodable binary codes whose pairwise distances depend on message compatibility rather than a single minimum distance. The construction is explicit and provably beats the classical Plotkin 1/4 barrier.
AI-written summary · about
chapters (15)
- 0:00Interactive coding breakthrough
- 1:09Error correcting codes basics
- 3:01Breaking Plotkin bound
- 7:18Key tasks in interactive coding
- 8:50Message resilience limits
- 12:29Message exchange over alphabets
- 17:36Open questions in adaptive coding
- 19:25Message transfer with feedback
- 21:57Error-resilience barriers
- 26:11Feedback for 1/3 error rate
- 27:35Three-round protocol
- 34:11Extending message transfer obstacles
- 36:42Why 1/4 seemed best
- 38:09Plotkin bound's persistence
- 38:54Q&A
related talks
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
41mHigh-Rate Fair-Density Parity-Check Codes
58mBosonic (And Other) Codes With Interesting Logical Gate Sets
32mComputational Wiretap Coding from Indistinguishability Obfuscation
43mCode-based Cryptography
19mError Correcting Codes for Uncompressed Messages
01h 00mError-Correcting Codes That Enable Efficient SNARKs
01h 10mNon-Malleable Codes in the Split-State Model