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 n1+o(1) and space no(1). In this work we focus on deterministic decoding. Gronemeier showed that any non-adaptive deterministic decoder for a good code running in time n1+δ must use space n1−δ. In sharp contrast, we show that all typical locally correctable codes have (non-uniform) time and space efficient adaptive deterministic decoders. 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 n1 + γ and space nγ by a uniform, deterministic decoder. A related construction allows us to uniformly decode asymptotically good codes based on lifted Reed-Solomon codes in time n1+o(1) and space no(1).