Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-045 | 4th April 2022 13:13

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring


Authors: Gil Cohen, Tal Yankovitz
Publication: 4th April 2022 17:48
Downloads: 173


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