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.
1: Added 2 notable references:
a: A reference to On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from
Symmetric-Key Primitive by Bangalore, Bhadauria, Hazay and Venkitasubramaniam which gives lower bounds for encoding codes, but in the more limited streaming model of computation.
b: A reference to Time and Space Efficient Deterministic Decoders by the same authors which gives codes with efficient deterministic decoders.
2: Added a small section to the intro explaining implications for PCP lower bounds.
3: Removed the open problem about finding codes with time and space efficient deterministic decoders because this has been resolved.
4: Many minor changes to fix typos, simplify theorem statements, and improve exposition.
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.
