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 [Gro06] showed that any nonadaptive deterministic decoder for a good code running in time n 1+δ must use space n 1-δ .

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 [Kop+17] 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 γ > 0, we give asymptotically good Reed-Muller codes that are decodable in time n 1+γ and space n γ by a uniform, deterministic decoder.