Locally Decodable Codes with Randomized Encoding
We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a...
Guardat en:
| Autors principals: | , , |
|---|---|
| Format: | Article |
| Publicat: |
2020
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2001.03692 http://arxiv.org/abs/2001.03692 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|
| _version_ | 1879172064015810560 |
|---|---|
| author | Cheng, Kuan Li, Xin Zheng, Yu |
| author_browse | Cheng, Kuan Li, Xin Zheng, Yu |
| author_facet | Cheng, Kuan Li, Xin Zheng, Yu |
| author_sort | Cheng, Kuan |
| building | arXiv |
| collection | Acceso abierto |
| description | We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword. This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time. Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity.
However, despite extensive research, the tradeoff between the rate of the code and the number of queries is somewhat disappointing. For example, the best known constructions still need super-polynomially long codeword length even with a logarithmic number of queries, and need a polynomial number of queries to achieve a constant rate. In this paper, we show that by using a randomized encoding, in several models we can achieve significantly better rate-query tradeoff. In addition, our codes work for both the standard Hamming errors, and the more general and harder edit errors. |
| first_indexed | 2026-10-15T23:35:24Z |
| 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-2001.03692</identifier><datestamp>2020-01-14</datestamp>
<dc:title>Locally Decodable Codes with Randomized Encoding</dc:title>
<dc:creator>Cheng, Kuan</dc:creator>
<dc:creator>Li, Xin</dc:creator>
<dc:creator>Zheng, Yu</dc:creator>
<dc:subject>Information Theory</dc:subject>
<dc:description>We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword. This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time. Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity.
However, despite extensive research, the tradeoff between the rate of the code and the number of queries is somewhat disappointing. For example, the best known constructions still need super-polynomially long codeword length even with a logarithmic number of queries, and need a polynomial number of queries to achieve a constant rate. In this paper, we show that by using a randomized encoding, in several models we can achieve significantly better rate-query tradeoff. In addition, our codes work for both the standard Hamming errors, and the more general and harder edit errors. </dc:description>
<dc:description>23 pages</dc:description>
<dc:date>2020-01-11</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2001.03692</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2001.03692</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2001.03692 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:35:24Z |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| record_format | oai_dc |
| spelling | arxiv-2001.036922020-01-14 Locally Decodable Codes with Randomized Encoding Cheng, Kuan Li, Xin Zheng, Yu Information Theory We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword. This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time. Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity. However, despite extensive research, the tradeoff between the rate of the code and the number of queries is somewhat disappointing. For example, the best known constructions still need super-polynomially long codeword length even with a logarithmic number of queries, and need a polynomial number of queries to achieve a constant rate. In this paper, we show that by using a randomized encoding, in several models we can achieve significantly better rate-query tradeoff. In addition, our codes work for both the standard Hamming errors, and the more general and harder edit errors. 23 pages 2020-01-11 text https://arxiv.org/abs/2001.03692 http://arxiv.org/abs/2001.03692 |
| spellingShingle | Information Theory Cheng, Kuan Li, Xin Zheng, Yu Locally Decodable Codes with Randomized Encoding |
| title | Locally Decodable Codes with Randomized Encoding |
| title_full | Locally Decodable Codes with Randomized Encoding |
| title_fullStr | Locally Decodable Codes with Randomized Encoding |
| title_full_unstemmed | Locally Decodable Codes with Randomized Encoding |
| title_short | Locally Decodable Codes with Randomized Encoding |
| title_sort | locally decodable codes with randomized encoding |
| topic | Information Theory |
| url | https://arxiv.org/abs/2001.03692 http://arxiv.org/abs/2001.03692 |
| work_keys_str_mv | AT chengkuan locallydecodablecodeswithrandomizedencoding AT lixin locallydecodablecodeswithrandomizedencoding AT zhengyu locallydecodablecodeswithrandomizedencoding |