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 TR22-045 | 10th August 2022 08:59

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

RSS-Feed




Revision #1
Authors: Gil Cohen, Tal Yankovitz
Accepted on: 10th August 2022 08:59
Downloads: 568
Keywords: 


Abstract:

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted codeword. An RLDC, however, is allowed to abort when identifying corruption. The natural analog to locally correctable codes, dubbed relaxed locally correctable codes (RLCC), was introduced by Gur, Ramnarayan and Rothblum (ITCS 2018) who constructed asymptotically-good length-$n$ RLCC and RLDC with $(\log{n})^{O(\log\log{n})}$ queries.

In this work we construct asymptotically-good RLDC and RLCC with an improved query complexity of $(\log{n})^{O(\log\log\log{n})}$. To achieve this, we devise a mechanism--an alternative to the tensor product--that squares the length of a given code. Compared to the tensor product that was used by Gur et al. and by many other constructions, our mechanism is significantly more efficient in terms of rate deterioration, allowing us to obtain our improved construction.



Changes to previous version:

Fixing a slightly inaccurate argument in the proof of Claim 4.2 as well as some minor modifications.


Paper:

TR22-045 | 4th April 2022 13:13

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring





TR22-045
Authors: Gil Cohen, Tal Yankovitz
Publication: 4th April 2022 17:48
Downloads: 650
Keywords: 


Abstract:

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted codeword. An RLDC, however, is allowed to abort when identifying corruption. The natural analog to locally correctable codes, dubbed relaxed locally correctable codes (RLCC), was introduced by Gur, Ramnarayan and Rothblum (ITCS 2018) who constructed asymptotically-good length-$n$ RLCC and RLDC with $(\log{n})^{O(\log\log{n})}$ queries.

In this work we construct asymptotically-good RLDC and RLCC with an improved query complexity of $(\log{n})^{O(\log\log\log{n})}$. To achieve this, we devise a mechanism--an alternative to the tensor product--that squares the length of a given code. Compared to the tensor product that was used by Gur et al. and by many other constructions, our mechanism is significantly more efficient in terms of rate deterioration, allowing us to obtain our improved construction.



ISSN 1433-8092 | Imprint