License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.1
URN: urn:nbn:de:0030-drops-142750
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14275/
Go to the corresponding LIPIcs Volume Portal

Cohen, Gil ; Yankovitz, Tal

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

pdf-format:
LIPIcs-CCC-2021-1.pdf (1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{cohen_et_al:LIPIcs.CCC.2021.1,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{1:1--1:57},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14275},
  URN =		{urn:nbn:de:0030-drops-142750},
  doi =		{10.4230/LIPIcs.CCC.2021.1},
  annote =	{Keywords: Locally decodable codes, Locally correctable codes}
}

Keywords: Locally decodable codes, Locally correctable codes
Collection: 36th Computational Complexity Conference (CCC 2021)
Issue Date: 2021
Date of publication: 08.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI