Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-104 | 26th February 2019 22:12

Local List Recovery of High-rate Tensor Codes & Applications

RSS-Feed




Revision #1
Authors: Brett Hemenway, Noga Ron-Zewi, Mary Wootters
Accepted on: 26th February 2019 22:12
Downloads: 616
Keywords: 


Abstract:

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.


Paper:

TR17-104 | 13th June 2017 22:27

Local List Recovery of High-rate Tensor Codes & Applications





TR17-104
Authors: Brett Hemenway, Noga Ron-Zewi, Mary Wootters
Publication: 14th June 2017 11:44
Downloads: 929
Keywords: 


Abstract:

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