__
TR24-110 | 1st July 2024 04:45
__

#### Time and Space Efficient Deterministic Decoders

TR24-110
Authors:

Joshua Cook,

Dana Moshkovitz
Publication: 1st July 2024 15:31

Downloads: 115

Keywords:

Curve Sampler,

decoding,

derandomization,

deterministic,

epsilon-biased sets,

Error correcting code,

explicit construction,

Locally Correctable Code,

low degree,

polynomial,

Sampler,

Subspace,

Time and Space Complexity
**Abstract:**
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.