Good codes decodable by linear-sized circuits?

Question

I'm looking for error-correcting codes of the following type:

binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.

Some background:

Spielman, in Linear-Time Encodable and Decodable Error-Correcting Codes, gave codes decodable in $O(N)$ time in the logarithmic-cost RAM model, and also decodable by $O(N \log N)$-sized circuits.
Guruswami and Indyk gave an improved construction in Linear Time Encodable/Decodable Codes with Near-Optimal Rate. They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.

Thanks in advance!

Andy, coincidentally, I also came across this issue about a year ago and after a brief amount of searching, concluded that the question was open. So, I'm also curious if an answer's known. — arnab, Apr 12 '11 at 23:45
This ECCC Report just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit. — Peter Shor, Apr 16 '11 at 18:15
Is $O(N)$ decoding achievable in the AWGN model or the binary model? — Turbo, Sep 20 '13 at 14:00
Good binary codes which are completely linear time ($O(N)$) encodable and decodable and achieve an error rate $2^{-N}$ where $N$ is block length of the code probably requires some fundamentally new idea. The best so far is along the lines of theorem $1$ in http://arxiv.org/pdf/1304.4321v2.pdf. Lets see if someone improves the $2^{-N^{0.49}}$ to $2^{-N^{1-\mu}}$ in there in $N^{1+\epsilon}$ encoding and decoding time which I believe should be possible (even with $\mu=0$). However, bringing $\epsilon$ to $0$ may need more than a few tricks. — Turbo, Dec 04 '13 at 19:58
Have a look at Expander codes. These codes achieve linear time coding and decoding. The linearity is w.r.t to the size of the codeword. But I am not sure if they can be decoded using linear circuits. — Vivek Bagaria, Apr 28 '14 at 11:28

score 2 · Answer 1 · answered Jun 11 '14 at 01:16

You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of bits in time proportional to $n \ln \frac{1}{\epsilon}$ (see Theorem 1 in {1}).

{1} Luby, Michael G., et al. "Practical loss-resilient codes." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

Good codes decodable by linear-sized circuits?

1 Answers1