Local List Recovery of High-rate Tensor Codes and Applications

Understand

In this work, we give the first construction of high-rate locally list-recoverable codes.

• List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.
• In particular, our construction gives the first capacity-achieving locally list-decodable codes (over constant-sized alphabet); the first capacity achieving globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known.
• Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes.