On Embeddings of ${\ell }_1^k$ from Locally Decodable Codes

Abstract

We show that any $q$-query locally decodable code (LDC) gives a copy of ${\ell }_1^k$ with small distortion in the Banach space of $q$-linear forms on ${\ell }_{p_1}^N\times \cdots \times {\ell }_{p_q}^N$, provided $1/p_1+\cdots +1/p_q\le 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit the copy of ${\ell }_1^k$ by constructing a basis for it directly from "smooth" LDC decoders. Based on this, we give alternative proofs for known lower bounds on the length of 2-query LDCs. Using similar techniques, we reprove known lower bounds for larger $q$. We also discuss the relation with an alternative proof, due to Pisier, of a result of Naor, Regev, and the author on cotype properties of projective tensor products of ${\ell }_p$ spaces.

Appeared earlier on ECCC (http://eccc.hpi-web.de/report/2015/086/). This version has a slightly shorter abstract and slightly edited introduction. Removed left-over notes

Cited by in corpus (1)

• Gaussian width bounds with applications to arithmetic progressions in random settings