Lower Bounds for Approximate LDCs
Author(s): Briët, Jop; Dvir, Zeev; Hu, Guangda; Saraf, Shubhangi
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1dc2v
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). |
Publication Date: | 2014 |
Citation: | Briët, Jop, Zeev Dvir, Guangda Hu, and Shubhangi Saraf. "Lower Bounds for Approximate LDCs." International Colloquium on Automata, Languages, and Programming (2014): pp. 259-270. doi:10.1007/978-3-662-43948-7_22 |
DOI: | 10.1007/978-3-662-43948-7_22 |
ISSN: | 0302-9743 |
EISSN: | 1611-3349 |
Pages: | 259 - 270 |
Type of Material: | Conference Article |
Journal/Proceeding Title: | International Colloquium on Automata, Languages, and Programming |
Version: | Author's manuscript |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.