Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-110 | 1st July 2024 04:45

Time and Space Efficient Deterministic Decoders



Time 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.

ISSN 1433-8092 | Imprint