Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-026 | 27th February 2014 16:55

Lower Bounds for Approximate LDCs

RSS-Feed




TR14-026
Authors: Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf
Publication: 27th February 2014 17:01
Downloads: 2854
Keywords: 


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 $(\alpha,\delta)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $\Omega(\delta n)$ disjoint $q$-tuples $(\vec{u}_1,\ldots,\vec{u}_q) $ in $V$ so that $\text{span}(\vec{u}_1,\ldots,\vec{u}_q)$ contains a unit vector whose $i$'th coordinate is at least $\alpha$. We prove exponential lower bounds of the form $n \geq 2^{\Omega(\alpha \delta \sqrt{d})}$ for the case $q=2$ and, in some cases, stronger bounds (exponential in $d$).



ISSN 1433-8092 | Imprint