Lower Bounds for Approximate LDCs

Abstract

We study an approximate version of q-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A q-query (α,δ)-approximate LDC is a set V of n points in ℝ d so that, for each i ∈ [d] there are Ω(δn) disjoint q-tuples (u 1,…,u q ) in V so that span(u 1,…,u q ) contains a unit vector whose i’th coordinate is at least α. We prove exponential lower bounds of the form 𝑛≥2Ω(𝛼𝛿𝑑√) for the case q = 2 and, in some cases, stronger bounds (exponential in d).