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 TR19-056 | 25th April 2019 12:02

A Lower Bound for Relaxed Locally Decodable Codes

RSS-Feed




Revision #1
Authors: Tom Gur, Oded Lachish
Accepted on: 25th April 2019 12:02
Downloads: 117
Keywords: 


Abstract:

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of O(1)-query LDCs have super-polynomial blocklength.

The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O(1)-query relaxed LDCs achieve blocklength n = O(k^{1+ \gamma}) for an arbitrarily small constant \gamma.

We prove a lower bound which shows that O(1)-query relaxed LDCs cannot achieve blocklength n = k^{1+ o(1)}. This resolves an open problem raised by Goldreich in 2004.



Changes to previous version:

Corrected references


Paper:

TR19-056 | 11th April 2019 23:45

A Lower Bound for Relaxed Locally Decodable Codes





TR19-056
Authors: Tom Gur, Oded Lachish
Publication: 14th April 2019 11:31
Downloads: 245
Keywords: 


Abstract:

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of O(1)-query LDCs have super-polynomial blocklength.

The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O(1)-query relaxed LDCs achieve blocklength n = O(k^{1+ \gamma}) for an arbitrarily small constant \gamma.

We prove a lower bound which shows that O(1)-query relaxed LDCs cannot achieve blocklength n = k^{1+ o(1)}. This resolves an open problem raised by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004).



ISSN 1433-8092 | Imprint