Lower Bounds for Approximate LDC

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,\dots ,{\vec{u}}_q)$ in $V$ so that $\text{span}({\vec{u}}_1,\dots ,{\vec{u}}_q)$ contains a unit vector whose $i$'th coordinate is at least $\alpha$. We prove exponential lower bounds of the form $n\ge 2^{\Omega (\alpha \delta \sqrt{d})}$ for the case $q=2$ and, in some cases, stronger bounds (exponential in $d$).

References in corpus (2)

• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Locally decodable codes and the failure of cotype for projective tensor products