Asymptotically-Good RLCCs with (log n)^{2+o(1)} Queries
summary
Constructs asymptotically good RLCCs with (log n)^{2+o(1)} queries by replacing full LTCs in the Kumar Mon reduction with vanilla expander codes that satisfy a weaker vicinity LTC property. This drops the previous exponent from 69 down to 2 up to subpolynomial factors, gives nonexplicit codes with near-constant rate approaching the near-GV rate, and uses unique neighbor expanders plus Sipser Spielman style decoding to make the reduction and correctness arguments go through.
AI-written summary · about
chapters (9)
- 0:00RLCCs introduction
- 2:20Lower bounds for high-rate RLCCs
- 6:32Previous progress and open problems
- 10:40Reduction LTCs to RLCCs
- 21:37LTCs necessity for RLCCs?
- 23:27Expander codes and vicinity LTCs
- 32:12Query complexity and rate
- 36:02Final construction parameters
- 39:21Conclusion and open questions
related talks
01h 09mWhen Cryptography Meets Modern Channel Coding
52mAn LLL Algorithm for Module Lattices
41mHigh-Rate Fair-Density Parity-Check Codes
37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
01h 08mCryptography from Ideal Lattices
26mPCPs and Instance Compression from a Cryptographic Lens
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions