ECCC-Report TR24-110https://eccc.weizmann.ac.il/report/2024/110Comments and Revisions published for TR24-110en-usMon, 01 Jul 2024 15:31:28 +0300
Paper TR24-110
| Time and Space Efficient Deterministic Decoders |
Joshua Cook,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2024/110Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.
Gronemeier showed that any non-adaptive deterministic decoder for a good code running in time $n^{1+\delta}$ must use space $n^{1-\delta}$.
In sharp contrast, we show that typical locally correctable codes have (non-uniform) time and space efficient deterministic decoders. For instance, the constant rate, constant relative distance codes with sub-linear query complexity of have non-uniform deterministic decoders running in time $n^{1+o(1)}$ and space $n^{o(1)}$. The same is true for Reed-Muller codes and multiplicity codes.
To obtain the decoders we devise a new time-space efficient derandomization technique that works by iterative correction.
Further, we give a new construction of curve samplers that allow us to uniformly decode Reed-Muller codes time and space efficiently. In particular, for any constant $\gamma > 0$, we give asymptotically good Reed-Muller codes that are decodable in time $n^{1 + \gamma}$ and space $n^\gamma$ by a uniform, deterministic decoder.Mon, 01 Jul 2024 15:31:28 +0300https://eccc.weizmann.ac.il/report/2024/110