Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
summary
Proves that any binary linear 3-query LCC of block length n has dimension k ≤ O_δ(log^2 n · log log n), nearly matching quadratic Reed–Muller (Θ(log^2 n)). Argument bounds the covering radius of the dual ≤ Õ_δ(log n) by showing every message is a Õ_δ(log n)-sparse linear combination of generator rows; proof iteratively shrinks large combinations and crucially applies the rainbow cycle theorem of Alon, Bučić, Sauermann, Zakharov, and Zamir (2023). Results improve prior log^8 / log^4 bounds.
AI-written summary · about
chapters (19)
- 0:00Locally correctable codes intro
- 1:54LCC lower bounds history
- 3:20Main results motivation
- 6:34Covering radius and dual codes
- 8:07Combinatorial proof reinterpretation
- 11:17Rainbow cycle problem reduction
- 14:47Binary linear 3-LCCs definition
- 16:10Inspiration from Iceland work
- 22:15Swapping game rules
- 25:08Edge-colored graph construction
- 28:25Graph simplification via deletions
- 29:10Rainbow cycle theorem application
- 30:59Swapping game to sum shifting
- 33:24Swapping game statistics
- 35:593-LCC lower bound proof
- 36:21Generalizing to odd q-query LCCs
- 37:48Rainbow LDCs role
- 39:58Open questions future
- 40:39Q&A on linearity
related talks
01h 09mWhen Cryptography Meets Modern Channel Coding
52mAn LLL Algorithm for Module Lattices
37mAlgebraic Algorithms for LWE
01h 00mError-Correcting Codes That Enable Efficient SNARKs
41mHigh-Rate Fair-Density Parity-Check Codes
51mMultilinear Maps and Attacks II
01h 08mCryptography from Ideal Lattices
01h 06mAlgorithms for the k-List Problems