Error Correcting Codes for Uncompressed Messages

on YouTube ↗19m

" summary

Defines codes for polynomial-time recognizable message sets S and proves for up to 3% adversarial errors an efficiently encodable/decodable randomized code with 1.74K encoding length for K-bit messages in S, improving on previous whole-space bounds of 2.52K (deterministic) and 2.27K (randomized). Construction relies on list decoding plus hashing the message space via a pairwise independent permutation so the decoder’s list contains at most one element of S with high probability.

AI-written summary · about

" chapters (5)

1. 0:00Setting and motivation
2. 3:27Defining codes for sets
3. 8:03Theorem and parameters
4. 13:44List decoding construction
5. 17:53Conclusion and implications

" related talks

• 44mCoding Theory in Almost Linear Time and Sublinear SpaceDana Moshkovitz · Advances in the Theory of Error-Correcting Codes
• 01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other TopicsAllison Bishop · The Mathematics of Modern Cryptography
• 01h 00mError-Correcting Codes That Enable Efficient SNARKsHadas Zeilberger · Proofs (Simons Institute)
• 35mBinary Error Correcting Codes with Minimal Noiseless FeedbackRachel Zhang · Advances in the Theory of Error-Correcting Codes
• 41mHigh-Rate Fair-Density Parity-Check CodesHessam Mahdavifar · Application-Driven Coding Theory 2024
• 39mGilbert and Varshamov meet Johnson: List Decoding Nearly-Optimal Binary CodesSilas Richelson · Advances in the Theory of Error-Correcting Codes
• 52mFast list-decoding of univariate multiplicity and folded Reed-Solomon codesPrahladh Harsha · Advances in the Theory of Error-Correcting Codes
• 04mError-Correcting Codes: Theory and PracticeVenkat Guruswami · 9th Annual Simons Institute Industry Day