The 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.
In the original version of this paper a rate amplification procedure is constructed for a certainly natural subset of linear LCC. In this revision, we further show that this subset in fact consists of all linear LCC.
In 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.
