ECCC-Report TR20-084https://eccc.weizmann.ac.il/report/2020/084Comments and Revisions published for TR20-084en-usWed, 03 Jun 2020 16:03:27 +0300
Paper TR20-084
| Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes |
Gil Cohen,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2020/084In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good $n$-bit locally decodable codes (LDC) with $2^{\widetilde{O}(\sqrt{\log{n}})}$ queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance $\delta$ of a code to a constant at a $\mathrm{poly}(1/\delta)$ multiplicative cost in query complexity. Given the pivotal role of the AEL distance amplification procedure in the state-of-the-art constructions of LDC as well as LCC and LTC, one is prompt to ask whether the $\mathrm{poly}(1/\delta)$ factor in query complexity can be reduced.
Our first contribution is a significantly improved distance amplification procedure for LDC. The cost is reduced from $\mathrm{poly}(1/\delta)$ to, roughly, the query complexity of a length $1/\delta$ asymptotically good LDC. We derive several applications, one of which allows us to convert a $q$-query LDC with extremely poor distance $\delta = n^{-(1-o(1))}$ to a constant distance LDC with $q^{\mathrm{poly}(\log\log{n})}$ queries. As another example, amplifying distance $\delta = 2^{-(\log{n})^\alpha}$, for any constant $\alpha < 1$, will require $q^{O(\log\log\log{n})}$ queries using our procedure.
Motivated by the fruitfulness of distance amplification, we investigate the natural question of rate amplification. Our second contribution is identifying a rich and natural class of LDC and devise two (incomparable) rate amplification procedures for it. These, however, deteriorate the distance, at which point a distance amplification procedure is invoked. Combined, the procedures convert any $q$-query LDC in our class, having rate $\rho$ and, say, constant distance, to an asymptotically good LDC with $q^{\mathrm{poly}(1/\rho)}$ queries.Wed, 03 Jun 2020 16:03:27 +0300https://eccc.weizmann.ac.il/report/2020/084