On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for...
محفوظ في:
| المؤلفون الرئيسيون: | , , , , , , |
|---|---|
| التنسيق: | مقال |
| منشور في: |
2022
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://arxiv.org/abs/2209.08688 http://arxiv.org/abs/2209.08688 |
| الوسوم: |
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1879174030434500608 |
|---|---|
| author | Block, Alex Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_browse | Block, Alex Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_facet | Block, Alex Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_sort | Block, Alex |
| building | arXiv |
| collection | Acceso abierto |
| description | Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs. |
| first_indexed | 2026-10-16T00:06:38Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2209.08688</identifier><datestamp>2022-09-20</datestamp>
<dc:title>On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors</dc:title>
<dc:creator>Block, Alex</dc:creator>
<dc:creator>Blocki, Jeremiah</dc:creator>
<dc:creator>Cheng, Kuan</dc:creator>
<dc:creator>Grigorescu, Elena</dc:creator>
<dc:creator>Li, Xin</dc:creator>
<dc:creator>Zheng, Yu</dc:creator>
<dc:creator>Zhu, Minshen</dc:creator>
<dc:subject>Information Theory</dc:subject>
<dc:subject>Computational Complexity</dc:subject>
<dc:description>Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs. </dc:description>
<dc:date>2022-09-19</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2209.08688</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2209.08688</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2209.08688 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:06:38Z |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| record_format | oai_dc |
| spelling | arxiv-2209.086882022-09-20 On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors Block, Alex Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen Information Theory Computational Complexity Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs. 2022-09-19 text https://arxiv.org/abs/2209.08688 http://arxiv.org/abs/2209.08688 |
| spellingShingle | Information Theory Computational Complexity Block, Alex Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title | On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title_full | On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title_fullStr | On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title_full_unstemmed | On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title_short | On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors |
| title_sort | on relaxed locally decodable codes for hamming and insertion deletion errors |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2209.08688 http://arxiv.org/abs/2209.08688 |
| work_keys_str_mv | AT blockalex onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT blockijeremiah onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT chengkuan onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT grigorescuelena onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT lixin onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT zhengyu onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors AT zhuminshen onrelaxedlocallydecodablecodesforhammingandinsertiondeletionerrors |