An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
summary
Proves that any linear 3‑query LCC C:{0,1}^k→{0,1}^n must have blocklength n ≥ exp(k^{1/8}), giving the first separation between q‑query LCCs and LDCs; shows design 3‑LCCs satisfy n ≥ 2^{(1‑o(1))√k} and extends to nonlinear LCCs with a superpolynomial k^{log k} bound. Proof lifts codewords to subset parities, reduces 3‑query LCCs to a 2‑query LDC by forming chain derivations producing longer parity checks, then finds large matchings via row‑pruning and Kim‑Vu style concentration.
AI-written summary · about
chapters (14)
- 0:00Locally correctable codes intro
- 1:47Motivation for LCCs
- 3:12Existence of LCCs
- 4:343-query LCCs in 2022
- 8:492024 breakthroughs
- 15:09Proof strategy overview
- 18:00Combinatorial form of linear 3-LCCs
- 20:38Reduction to 2-query LDCs
- 23:26Graph with large avg degree
- 27:50Chaining constraints
- 32:28Row-pruning for bounded degree
- 37:06Exponential lower bound
- 37:28Open problems
- 42:49Summary
related talks
01h 06mAlgorithms for the k-List Problems
01h 09mWhen Cryptography Meets Modern Channel Coding
34mHigh-entropy dual functions and locally decodable codes
41mHigh-Rate Fair-Density Parity-Check Codes
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
52mAn LLL Algorithm for Module Lattices
01h 00mError-Correcting Codes That Enable Efficient SNARKs
51mMultilinear Maps and Attacks II