A Lower Bound for Relaxed Locally Decodable Codes

Understand

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.