  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.
