List-decodable zero-rate codes
We consider list decoding in the zero-rate regime for two cases: the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ϵ [0,1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension)...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/124995 |
| _version_ | 1826207944241315840 |
|---|---|
| author | Alon, Noga Bukh, Boris Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Alon, Noga Bukh, Boris Polyanskiy, Yury |
| author_sort | Alon, Noga |
| collection | MIT |
| description | We consider list decoding in the zero-rate regime for two cases: the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ϵ [0,1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by L or more of them. As M → ∞ the maximal τ decreases to a well-known critical value T[subscript L]. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ (M-¹) when L is even, thus extending the classical results of Plotkin and Levenshtein for L=2. For L=3 , the rate is shown to be Θ (M -(2/3) ). For the similar question about spherical codes, we prove the rate is Ω (M-¹) and O([mathematical figure; see resource]). ©2019 |
| first_indexed | 2024-09-23T13:57:25Z |
| format | Article |
| id | mit-1721.1/124995 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:57:25Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1249952022-10-01T18:15:16Z List-decodable zero-rate codes Alon, Noga Bukh, Boris Polyanskiy, Yury Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We consider list decoding in the zero-rate regime for two cases: the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ϵ [0,1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by L or more of them. As M → ∞ the maximal τ decreases to a well-known critical value T[subscript L]. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ (M-¹) when L is even, thus extending the classical results of Plotkin and Levenshtein for L=2. For L=3 , the rate is shown to be Θ (M -(2/3) ). For the similar question about spherical codes, we prove the rate is Ω (M-¹) and O([mathematical figure; see resource]). ©2019 2020-05-04T16:32:23Z 2020-05-04T16:32:23Z 2019-03 2019-07-01T18:02:41Z Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 https://hdl.handle.net/1721.1/124995 Alon, Noga, Boris Bukh, and Yury Polyanskiy, "List-decodable zero-rate codes." IEEE Transactions on Information Theory 65, 3 (Mar. 2019): p. 1657-67 doi 10.1109/TIT.2018.2868957 ©2019 Author(s) en 10.1109/TIT.2018.2868957 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Alon, Noga Bukh, Boris Polyanskiy, Yury List-decodable zero-rate codes |
| title | List-decodable zero-rate codes |
| title_full | List-decodable zero-rate codes |
| title_fullStr | List-decodable zero-rate codes |
| title_full_unstemmed | List-decodable zero-rate codes |
| title_short | List-decodable zero-rate codes |
| title_sort | list decodable zero rate codes |
| url | https://hdl.handle.net/1721.1/124995 |
| work_keys_str_mv | AT alonnoga listdecodablezeroratecodes AT bukhboris listdecodablezeroratecodes AT polyanskiyyury listdecodablezeroratecodes |