Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best construction...
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| 格式: | Artículo |
| 出版: |
2026
|
| 主題: | |
| 在線閱讀: | https://arxiv.org/abs/2602.20278 http://arxiv.org/abs/2602.20278 |
| 標簽: |
沒有標簽, 成為第一個標記此記錄!
|
| _version_ | 1879178443765055488 |
|---|---|
| author | Block, Alexander R. Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_browse | Block, Alexander R. Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_facet | Block, Alexander R. Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen |
| author_sort | Block, Alexander R. |
| building | arXiv |
| collection | Acceso abierto |
| description | Locally Decodable Codes (LDCs) are error-correcting codes $C\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^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, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show 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. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. |
| first_indexed | 2026-10-16T01:16:50Z |
| 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-2602.20278</identifier><datestamp>2026-03-03</datestamp>
<dc:title>Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes</dc:title>
<dc:creator>Block, Alexander R.</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\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^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, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show 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. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. </dc:description>
<dc:description>arXiv admin note: substantial text overlap with arXiv:2209.08688</dc:description>
<dc:date>2026-02-23</dc:date>
<dc:date>2026-02-28</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2602.20278</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2602.20278</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2602.20278 |
| institution | arXiv |
| last_indexed | 2026-10-16T01:16:50Z |
| publishDate | 2026 |
| publishDateRange | 2026 |
| publishDateSort | 2026 |
| record_format | oai_dc |
| spelling | arxiv-2602.202782026-03-03 Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes Block, Alexander R. 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\colonΣ^n\rightarrow Σ^m,$ encoding \emph{messages} in $Σ^n$ to \emph{codewords} in $Σ^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, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show 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. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. arXiv admin note: substantial text overlap with arXiv:2209.08688 2026-02-23 2026-02-28 text https://arxiv.org/abs/2602.20278 http://arxiv.org/abs/2602.20278 |
| spellingShingle | Information Theory Computational Complexity Block, Alexander R. Blocki, Jeremiah Cheng, Kuan Grigorescu, Elena Li, Xin Zheng, Yu Zhu, Minshen Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title | Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title_full | Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title_fullStr | Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title_full_unstemmed | Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title_short | Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes |
| title_sort | exponential lower bounds for 2 query relaxed locally decodable codes |
| topic | Information Theory Computational Complexity |
| url | https://arxiv.org/abs/2602.20278 http://arxiv.org/abs/2602.20278 |
| work_keys_str_mv | AT blockalexanderr exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT blockijeremiah exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT chengkuan exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT grigorescuelena exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT lixin exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT zhengyu exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes AT zhuminshen exponentiallowerboundsfor2queryrelaxedlocallydecodablecodes |