Binary Error Correcting Codes with Minimal Noiseless Feedback

on YouTube ↗35m

" summary

Presents optimal limited-feedback binary codes: constructs feedback codes (errors and erasures) that reach 1/3 adversarial error resilience using only O(log k) feedback bits over constantly many rounds and proves matching lower bounds that fewer-than-log-k feedback gives no improvement beyond the 1/4 one-way bound. Key tools are list decoding and a compressed, partitioned version of the modified Spencer‑Winkler coin game plus standard ECCs; rounds and feedback incur polynomial dependence on 1/epsilon and growing rounds are necessary to approach 1/3.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 1:12Error correcting codes basics
3. 3:40Standard vs feedback codes
4. 6:26Minimizing feedback
5. 10:43Erasure setting
6. 16:42Coin game paradigm
7. 24:03Spencer Winkler protocol
8. 28:21Modified protocol
9. 31:34Combining strategies
10. 32:18Results and open questions
11. 34:02Q&A

" related talks

• 01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other TopicsAllison Bishop · The Mathematics of Modern Cryptography
• 19mError Correcting Codes for Uncompressed MessagesOfer Grossman, Justin Holmgren · ITCS 2021
• 41mHigh-Rate Fair-Density Parity-Check CodesHessam Mahdavifar · Application-Driven Coding Theory 2024
• 01h 00mError-Correcting Codes That Enable Efficient SNARKsHadas Zeilberger · Proofs (Simons Institute)
• 01h 09mWhen Cryptography Meets Modern Channel CodingJoseph J. Boutros · Lattices: Geometry, Algorithms and Hardness 2020
• 32mComputational Wiretap Coding from Indistinguishability ObfuscationPaul Lou · Obfuscation
• 04mError-Correcting Codes: Theory and PracticeVenkat Guruswami · 9th Annual Simons Institute Industry Day
• 01h 07mComputing on Encrypted Data via Secret Dual CodesYuval Ishai · Obfuscation