TR09-115 Authors: Swastik Kopparty, Shubhangi Saraf

Publication: 14th November 2009 01:12

Downloads: 4433

Keywords:

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that for all constants $c> 0$ and $\gamma > 0$, and for every linear code $\mathcal C \subseteq \{0,1\}^N$ which is:

\begin{itemize}

\item {\em sparse}: $|\calC| \leq N^c$, and

\item {\em unbiased}: each nonzero codeword in $\mathcal C$ has weight $\in (\frac{1}{2} - N^{-\gamma}, \frac{1}{2} + N^{-\gamma})$,

\end{itemize}

$\mathcal C$ is locally testable and locally list-decodable from $(\frac{1}{2} - \epsilon)$-fraction worst-case errors using only $\poly(\frac{1}{\epsilon})$ queries to a received word. We also give {\em sub-exponential time} algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. In particular, this yields the first sub-exponential time algorithm even for the problem of (unique) decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors.

Earlier, Kaufman and Sudan had shown that sparse, unbiased codes

can be locally (unique) decoded and locally tested from a constant-fraction of errors, where this constant-fraction

tends to 0 as the number of codewords grows. Our results significantly strengthen their results, while also

having significantly simpler proofs.

At the heart of our algorithms is a natural ``self-correcting" operation defined on codes and received words.

This self-correcting operation transforms a code $\mathcal C$

with a received word $w$ into a simpler code $\mathcal C'$ and a related received word $w'$, such that $w$ is close to

$\mathcal C$ if and only if $w'$ is close to $\mathcal C'$.

Starting with a sparse, unbiased code $\mathcal C$ and an arbitrary received word $w$,

a constant number of applications of the self-correcting

operation reduces us to the case of local list-decoding and testing for the {\em Hadamard code}, for which the well known

algorithms of Goldreich-Levin and Blum-Luby-Rubinfeld are available. This yields the constant-query local algorithms for

the original code $\mathcal C$.

Our algorithm for decoding unbiased linear codes in sub-exponential time proceeds similarly. Applying the self-correcting operation to an unbiased code $\mathcal C$ and an arbitrary received word a

super-constant number of times, we get reduced to the problem of

{\em learning noisy parities}, for which non-trivial sub-exponential time algorithms were recently given by

Blum-Kalai-Wasserman and Feldman-Gopalan-Khot-Ponnuswami.

Our result generalizes a result of Lyubashevsky, which gave sub-exponential time algorithms for decoding random linear codes of inverse-polynomial rate, from {\em random errors}.