Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-032 | 22nd February 2024 00:28

Explicit Time and Space Efficient Encoders Exist Only With Random Access



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.

ISSN 1433-8092 | Imprint