## 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.