A Lower Bound for Relaxed Locally Decodable Codes

by Tom Gur and Oded Lachish

Oded's comments

This is a great result. Ever since 2004, I have been puzzled by the question of whether the relaxation of local decodability presented in BGHSV04 allows for almost linear codeword length in the sense that $k$-bit strings are encoded by strings of length $k^{1+o(1)}$. The current work answers this question negatively, providing a lower bound of the form $k^{1+\gamma}$, where $\gamma$ is a constant that depends on the constant query complexity of the decoder.

Although the lower bound on (strict) locally decodable codes (LDCs) has the same form (i.e., $k^{1+\gamma}), the upper bound on relaxed LDCs also has this form (but both are with different gamma's, which is - of course - a must for the upper bound...) Hence, a separation between relaxed and strict LDCs seems to call for improving the lower bounds on the strict LDCs, although a separation via an improvement of the upper bounds on relaxed LDCs is still a possibility.

The original 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 =3D 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 =3D k^{1+ o(1)}. This resolves an open problem raised by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004).

See ECCC TR19-056.


Back to list of Oded's choices.