ECCC-Report TR24-158https://eccc.weizmann.ac.il/report/2024/158Comments and Revisions published for TR24-158en-usWed, 06 Nov 2024 07:00:37 +0200
Revision 1
| Improved Explicit Near-Optimal Codes in the High-Noise Regimes |
Songtao Mao,
Xin Li
https://eccc.weizmann.ac.il/report/2024/158#revision1We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows.
1. Explicit Near-Optimal Linear Time Uniquely Decodable Codes: We construct a family of explicit $\mathbb{F}_2$-linear codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of correcting $e$ errors and $s$ erasures whenever $2e + s < (1 - \varepsilon)n$ in linear-time. To the best of our knowledge, this is the first fully explicit linear time decodable code over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier.
2. Explicit Near-Optimal List Decodable Codes: We construct a family of explicit list decodable codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of list decoding from $1-\varepsilon$ fraction of errors with a list size $L = \exp\exp\exp(\log^{\ast}n)$ in polynomial time. To the best of our knowledge, this is the first fully explicit list decodable code with polynomial-time list decoding over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier.
3. List Decodable Code with Near-Optimal List Size: We construct a family of explicit list decodable codes with an optimal list size of $O(1/\varepsilon)$, albeit with a suboptimal rate of $O(\varepsilon^2)$, capable of list decoding from $1-\varepsilon$ fraction of errors in polynomial time. Furthermore, we introduce a new combinatorial object called multi-set disperser, and use it to give a family of list decodable codes with near-optimal rate $\frac{\varepsilon}{\log^2(1/\varepsilon)}$ and list size $\frac{\log^2(1/\varepsilon)}{\varepsilon}$, that can be constructed in probabilistic polynomial time and decoded in deterministic polynomial time.
Our techniques are based on plurality analysis and graph-concatenated codes, which are widely used in the literature. We also introduce new decoding algorithms that may prove valuable for other graph-based codes.Wed, 06 Nov 2024 07:00:37 +0200https://eccc.weizmann.ac.il/report/2024/158#revision1
Paper TR24-158
| Improved Explicit Near-Optimal Codes in the High-Noise Regimes |
Songtao Mao,
Xin Li
https://eccc.weizmann.ac.il/report/2024/158We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows.
1. Explicit Near-Optimal Linear Time Uniquely Decodable Codes: We construct a family of explicit $\mathbb{F}_2$-linear codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of correcting $e$ errors and $s$ erasures whenever $2e + s < (1 - \varepsilon)n$ in linear-time. To the best of our knowledge, this is the first fully explicit linear time decodable code over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier.
2. Explicit Near-Optimal List Decodable Codes: We construct a family of explicit list decodable codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of list decoding from $1-\varepsilon$ fraction of errors with a list size $L = \exp\exp\exp(\log^{\ast}n)$ in polynomial time. To the best of our knowledge, this is the first fully explicit list decodable code with polynomial-time list decoding over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier.
3. List Decodable Code with Near-Optimal List Size: We construct a family of explicit list decodable codes with an optimal list size of $O(1/\varepsilon)$, albeit with a suboptimal rate of $O(\varepsilon^2)$, capable of list decoding from $1-\varepsilon$ fraction of errors in polynomial time. Furthermore, we introduce a new combinatorial object called multi-set disperser, and use it to give a family of list decodable codes with near-optimal rate $\frac{\varepsilon}{\log^2(1/\varepsilon)}$ and list size $\frac{\log^2(1/\varepsilon)}{\varepsilon}$, that can be constructed in probabilistic polynomial time and decoded in deterministic polynomial time.
Our techniques are based on plurality analysis and graph-concatenated codes, which are widely used in the literature. We also introduce new decoding algorithms that may prove valuable for other graph-based codes.Sat, 19 Oct 2024 19:03:41 +0300https://eccc.weizmann.ac.il/report/2024/158