### 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 n ≥ 2 ^{Ω(αδ√d)} for the case q = 2 and, in some cases, stronger bounds (exponential in d).

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings |

Publisher | Springer Verlag |

Pages | 259-270 |

Number of pages | 12 |

Edition | PART 1 |

ISBN (Print) | 9783662439470 |

DOIs | |

State | Published - Jan 1 2014 |

Event | 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark Duration: Jul 8 2014 → Jul 11 2014 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Number | PART 1 |

Volume | 8572 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 |
---|---|

Country | Denmark |

City | Copenhagen |

Period | 7/8/14 → 7/11/14 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Lower bounds for approximate LDCs'. Together they form a unique fingerprint.

## Cite this

Briët, J., Dvir, Z., Hu, G., & Saraf, S. (2014). Lower bounds for approximate LDCs. In

*Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings*(PART 1 ed., pp. 259-270). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_22