Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-069 | 6th May 2022 07:43

List-Decoding XOR Codes Near the Johnson Bound

RSS-Feed




Revision #1
Authors: Silas Richelson, Sourya Roy
Accepted on: 6th May 2022 07:43
Downloads: 774
Keywords: 


Abstract:

In 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}.


Paper:

TR22-069 | 28th April 2022 11:30

List-Decoding Random Walk XOR Codes Near the Johnson Bound





TR22-069
Authors: Silas Richelson, Sourya Roy
Publication: 5th May 2022 16:45
Downloads: 758
Keywords: 


Abstract:

In 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}.



ISSN 1433-8092 | Imprint