Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient \emph{randomized} decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on \emph{deterministic} decoding.
Gronemeier showed that any \emph{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 \emph{adaptive deterministic} decoders. For instance, the constant rate, constant relative distance codes with sub-linear query complexity of [KMRS17] have non-uniform deterministic decoders running in time $n^{1+o(1)}$ and space $n^{o(1)}$.
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 \emph{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. A related construction allows us to \emph{uniformly} decode asymptotically good codes based on lifted Reed-Solomon codes in time $n^{1+o(1)}$ and space $n^{o(1)}$.

1. Added uniform, almost linear time, sub-polynomial space deterministic decoders for asymptotically good codes based on lifted Reed-Solomon codes.
2. Various small changes to exposition, preliminaries.

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.