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