We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been a useful building block in the design of list decodable codes, and our motivation is to use the tensor construction as such a building block.
In particular, instantiating this construction with known constructions of high-rate globally list recoverable codes, and using appropriate transformations, we obtain the first {\em capacity-achieving} locally list decodable codes (over a large constant size alphabet), and the first capacity-achieving globally list decodable codes with {\em nearly linear time} list decoding algorithms.
Our techniques are inspired by an approach of Gopalan, Guruswami, and Raghavendra (SIAM Journal on Computing, 2011) for list decoding tensor codes.
In this work, we give the first construction of {\em 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 {\em capacity-achieving} locally list-decodable codes (over constant-sized alphabet); the first {\em 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. We show that tensor powers of (globally) list-recoverable codes are `approximately' locally list-recoverable, and that the `approximately' modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions
of high-rate globally list-recoverable codes
and high-rate locally decodable codes finishes the construction.