Relaxed Local Correctability from Local Testing
summary
Constructs the first asymptotically good relaxed locally correctable codes that use polylogarithmic queries to recover a target bit or output failure, closing the previous superpolynomial gap. The core method is nesting an RLCC inside an LTC at many scales: high-rate locally testable codes certify progressively smaller restrictions while a single recurse on the small corrector keeps the overhead an additive query cost per level (m ≈ log n / log log n), yielding constant rate and constant decoding radius.
AI-written summary · about
chapters (19)
- 0:00Introduction to RLCCs
- 0:20Defining relaxed LCCs
- 5:02Refining the RLCC definition
- 5:45Prior research and context
- 9:11The role of smoothness
- 9:41Lower and upper bounds
- 10:22Inductive approach
- 10:53Iterated tensor product
- 17:15Introducing LTCs as a tool
- 18:45The nesting operation
- 19:59Handling corruption cases
- 20:56Nesting mechanics
- 21:33Preserving code parameters
- 25:02Local corrector strategy
- 25:43Iterative construction
- 31:06Parameter instantiation
- 31:38Final construction results
- 35:15Closing remarks
- 36:28Q&A session
related talks
01h 09mWhen Cryptography Meets Modern Channel Coding
04mError-Correcting Codes: Theory and Practice
01h 00mError-Correcting Codes That Enable Efficient SNARKs
41mHigh-Rate Fair-Density Parity-Check Codes
01h 02mTree PCPs
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 01mLocal Proofs Approaching the Witness Length
01h 05mSuccinct Randomized Encodings from Lattices