ECCC-Report TR22-069https://eccc.weizmann.ac.il/report/2022/069Comments and Revisions published for TR22-069en-usFri, 06 May 2022 07:43:04 +0300
Revision 1
| List-Decoding XOR Codes Near the Johnson Bound |
Silas Richelson,
Sourya Roy
https://eccc.weizmann.ac.il/report/2022/069#revision1In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$ and thus it almost achieves the Gilbert-Varshamov bound, except for the $o(1)$ term in the exponent. The prior best list-decoding algorithm for (a variant of) Ta-Shma's code achieves is due to Alev et al (STOC 2021). This algorithm makes use of SDP hierarchies, and is able to recover from a $\frac{1-\rho}{2}-$fraction of errors as long as $\rho\geq2^{\log(1/\varepsilon)^{1/6}}$. In this work we give an improved analysis of a similar list-decoding algorithm. Our algorithm works for Ta-Shma's original code, and it is able to list-decode almost all the way to the Johnson bound: it can recover from a $\frac{1-\rho}{2}-$fraction of errors as long as $\rho\geq2\sqrt{\varepsilon}$.Fri, 06 May 2022 07:43:04 +0300https://eccc.weizmann.ac.il/report/2022/069#revision1
Paper TR22-069
| List-Decoding Random Walk XOR Codes Near the Johnson Bound |
Silas Richelson,
Sourya Roy
https://eccc.weizmann.ac.il/report/2022/069In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$ and thus it almost achieves the Gilbert-Varshamov bound, except for the $o(1)$ term in the exponent. The prior best list-decoding algorithm for (a variant of) Ta-Shma's code achieves is due to Alev et al (STOC 2021). This algorithm makes use of SDP hierarchies, and is able to recover from a $\frac{1-\rho}{2}-$fraction of errors as long as $\rho\geq2^{\log(1/\varepsilon)^{1/6}}$. In this work we give an improved analysis of a similar list-decoding algorithm. Our algorithm works for Ta-Shma's original code, and it is able to list-decode almost all the way to the Johnson bound: it can recover from a $\frac{1-\rho}{2}-$fraction of errors as long as $\rho\geq2\sqrt{\varepsilon}$.Thu, 05 May 2022 16:45:01 +0300https://eccc.weizmann.ac.il/report/2022/069