We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes described in [GHKPV13]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length.

In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access.