Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-084 | 31st May 2020 11:28

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


Authors: Gil Cohen, Tal Yankovitz
Publication: 3rd June 2020 16:03
Downloads: 308


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