ECCC-Report TR20-084https://eccc.weizmann.ac.il/report/2020/084Comments and Revisions published for TR20-084en-usTue, 29 Jun 2021 18:02:26 +0300
Revision 1
| Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC |
Gil Cohen,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2020/084#revision1The main contribution of this work is a rate amplification procedure for LCC. Our procedure converts any $q$-query linear LCC, having rate $\rho$ and, say, constant distance to an asymptotically good LCC with $q^{poly(1/\rho)}$ queries.
Our second contribution is a distance amplification procedure for LDC that converts any linear LDC with distance $\delta$ and, say, constant rate to an asymptotically good LDC. The query complexity only suffers a multiplicative overhead that is roughly equal to the query complexity of a length $1/\delta$ asymptotically good LDC. This improves upon the $poly(1/\delta)$ overhead obtained by the AEL distance amplification procedure due to Alon, Edmonds and Luby. (FOCS 1995, ).
Our work establishes that the construction of asymptotically good LDC and LCC is reduced, with a minor overhead in query complexity, to the problem of constructing a vanishing rate linear LCC and a (rapidly) vanishing distance linear LDC, respectively.Tue, 29 Jun 2021 18:02:26 +0300https://eccc.weizmann.ac.il/report/2020/084#revision1
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