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