Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-104 | 13th June 2017 22:27

Local List Recovery of High-rate Tensor Codes & Applications


Authors: Brett Hemenway, Noga Ron-Zewi, Mary Wootters
Publication: 14th June 2017 11:44
Downloads: 290


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.

ISSN 1433-8092 | Imprint