Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
复制标题
宽松的本地可解码和可纠正代码：超越张量
DOI：
10.1109/focs54457.2022.00010
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tal Yankovitz
中科院分区：
文献类型：
--
作者：
Gil Cohen;Tal Yankovitz
在他们极具影响力的论文中，Ben-Sasson，Goldreich，Harsha，Sudan和Vadhan（STOC 2004）引入了松弛局部可解码码（Released Local Decodable Code，RLDC）的概念。类似于本地可解码代码（Katz-Trevisan; STOC 2000），前者允许访问任何所需的消息符号，只需对可能损坏的码字进行几次查询。然而，RLDC在识别损坏时被允许中止。Gur，Ramnarayan and Rothblum（ITCS 2018）引入了与本地可纠正代码类似的自然代码，称为松弛本地可纠正代码（relaxed local correctable codes，RLCC），他们使用$（\log n）^{O（\log\log n）}$查询构建了渐进良好的长度nRLCC和RLDC。在这项工作中，我们构建了渐进良好的RLDC和RLCC，其查询复杂度为$（\log n）^{O（\log\log\log n）}$。为了实现这一点，我们设计了一种机制-一种替代张量积-平方给定代码的长度。与Gur等人和许多其他构造所使用的张量积相比，我们的机制在速率恶化方面显着更有效，使我们能够获得改进的构造。
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-nRLCC 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.
登录
查看更多内容
具有近线性块长度和恒定查询复杂度的宽松局部可纠正代码
影响因子：
1.6
作者：
Chiesa A
通讯作者：
Chiesa A
论宽松局部解码算法的威力
影响因子：
1.6
作者：
Gur T
通讯作者：
Gur T
影响因子：
2.5
作者：
Blocki, Jeremiah;Gandikota, Venkata;Grigorescu, Elena;Zhou, Samson
通讯作者：
Zhou, Samson
提升的多重性代码和不相交修复群属性
影响因子：
2.5
作者：
Li, Ray;Wootters, Mary
通讯作者：
Wootters, Mary