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 TR09-069 | 24th September 2009 11:59

A note on Efremenko's Locally Decodable Codes

RSS-Feed




Revision #1
Authors: Parikshit Gopalan
Accepted on: 24th September 2009 11:59
Downloads: 3976
Keywords: 


Abstract:

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally. In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.

A crucial ingredient in these codes is the construction of a large family of matching verctors. We present a simple and elegant construction due to Sudan which matches the best known construction.



Changes to previous version:

Sudan's construction of a large family of matching vectors.


Paper:

TR09-069 | 2nd September 2009 20:43

A note on Efremenko's Locally Decodable Codes





TR09-069
Authors: Parikshit Gopalan
Publication: 2nd September 2009 22:42
Downloads: 3921
Keywords: 


Abstract:

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.



ISSN 1433-8092 | Imprint