期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-78
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In a seminal work, Kopparty et al. [KMRZS17] constructed asymptotically good n-bit locally decodable codes (LDC) with 2Oe( √ log n) queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. [AL96, AEL95] which amplifies the distance δ of a code to a constant at a poly(1/δ) 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 poly(1/δ) factor in query complexity can be reduced. Our first contribution is a significantly improved distance amplification procedure for LDC. The cost is reduced from poly(1/δ) to, roughly, the query complexity of a length 1/δ asymptotically good LDC. We derive several applications, one of which allows us to convert a q-query LDC with extremely poor distance δ = n −(1−o(1)) to a constant distance LDC with q poly(log log n) queries. As another example, amplifying distance δ = 2−(log n) α , for any constant α < 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 ρ and, say, constant distance, to an asymptotically good LDC with q poly(1/ρ) queries.
