ECCC-Report TR15-086https://eccc.weizmann.ac.il/report/2015/086Comments and Revisions published for TR15-086en-usThu, 28 May 2015 14:37:30 +0300
Paper TR15-086
| On Embeddings of $\ell_1^k$ from Locally Decodable Codes |
Jop Briet
https://eccc.weizmann.ac.il/report/2015/086We 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 \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit the copies of $\ell_1^k$ by constructing a basis directly from "smooth" LDC decoders, thus bypassing a matching lemma often used in the LDC literature. 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.Thu, 28 May 2015 14:37:30 +0300https://eccc.weizmann.ac.il/report/2015/086