All reports by Author Silas Richelson:

__
TR22-069
| 28th April 2022
__

Silas Richelson, Sourya Roy#### List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

Silas Richelson, Sourya Roy

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) ... more >>>