Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-032 | 4th July 2024 05:28

Explicit Time and Space Efficient Encoders Exist Only With Random Access

RSS-Feed




Revision #1
Authors: Joshua Cook, Dana Moshkovitz
Accepted on: 4th July 2024 05:28
Downloads: 93
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR24-032 | 22nd February 2024 00:28

Explicit Time and Space Efficient Encoders Exist Only With Random Access


Abstract:

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