2026-08-09T04:20:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14275 2024-03-12T12:00:01Z ddc:004 open_access

Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC Cohen, Gil Yankovitz, Tal Locally decodable codes Locally correctable codes The main contribution of this work is a rate amplification procedure for LCC. Our procedure converts any q-query linear LCC, having rate ρ and, say, constant distance to an asymptotically good LCC with q^poly(1/ρ) queries. Our second contribution is a distance amplification procedure for LDC that converts any linear LDC with distance δ 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/δ asymptotically good LDC. This improves upon the poly(1/δ) overhead obtained by the AEL distance amplification procedure [Alon and Luby, 1996; Alon et al., 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gil Cohen and Tal Yankovitz 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.1 urn:nbn:de:0030-drops-142750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.1 eng https://creativecommons.org/licenses/by/4.0/legalcode