2014
Lower bounds for approximate LDCs
Publication
Publication
Presented at the
European Conference on Numerical Mathematics and Advanced Applications
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 (u1,...,uq) in V so that span(u 1,...,uq) contains a unit vector whose i'th coordinate is at least α. We prove exponential lower bounds of the form n ≥ 2 Ω(αδ√d) for the case q = 2 and, in some cases, stronger bounds (exponential in d).
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-662-43948-7_22 | |
| Lecture Notes in Computer Science | |
| European Conference on Numerical Mathematics and Advanced Applications | |
|
Briët, J., Dvir, Z. (Zeev), Hu, G. (Guangda), & Saraf, S. (Shubhangi). (2014). Lower bounds for approximate LDCs. In Lecture Notes in Computer Science. doi:10.1007/978-3-662-43948-7_22 |
|