Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-084 | 29th June 2021 18:02

Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC

RSS-Feed




Revision #1
Authors: Gil Cohen, Tal Yankovitz
Accepted on: 29th June 2021 18:02
Downloads: 521
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR20-084 | 31st May 2020 11:28

Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes





TR20-084
Authors: Gil Cohen, Tal Yankovitz
Publication: 3rd June 2020 16:03
Downloads: 876
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint